| 杨雪洁,曹风云,陈 洁,赵 姝,张燕平.基于子模优化的边界域处理社团发现算法[J].电子测量与仪器学报,2020,34(4):111-117 |
| 基于子模优化的边界域处理社团发现算法 |
| Community detection algorithm for boundary region processingbased on submodular optimization |
| |
| DOI： |
| 中文关键词: 子模函数 三支决策 复杂网络 社团发现 |
| 英文关键词:submodular function three-way decision complex networks community detection |
| 基金项目:国家自然科学基金(61673020,61602003)、安徽省自然科学基金 (1708085QF156)、安徽省高校优秀青年人才项目( gxyq2019068)、电子信息系统仿真设计安徽省重点实验室开放基金(2019ZDSYSZY06)资助项目 |
|
|
|
|
| 摘要点击次数: 468 |
| 全文下载次数: 447 |
| 中文摘要: |
| 使用聚类粒化方法求取非重叠社团结构时,经常会出现重叠区域。 三支决策模型将两个存在重叠的社团的左边社团中
非重叠部分定义为正域,右边社团中非重叠部分定义为负域,而两个社团的重叠部分定义为边界域。 为了获得更好的社团性
能,须将边界域中的节点进行二次划分。 子模优化在机器学习中有广泛的应用,如果目标函数具有子模性,则存在一个简单的
贪心算法能在多项式时间内以常数因子逼近问题的最优解。 将子模优化思想引入社团重叠区域节点的处理,提出一种基于子
模优化的边界域处理社团发现算法(SO-CDA)。 定义设备选址函数进行子模优化,重叠节点的划分可以转化为子模函数最大
化问题,在 7 个真实网络上的实验结果表明,SO-CDA 能够有效地进行社团划分,性能更加稳定。 |
| 英文摘要: |
| Overlapping regions often occur when non-overlapping community structure is obtained by clustering granulation method. The
nodes in the non-overlapping parts of the community of the left side between two communities with overlapping parts were defined as
positive regions. Then, the nodes on its right are denoted as the negative region, and nodes in the overlapping parts are denoted as the
boundary region. In order to achieve better community structure, it is necessary to divide the nodes in the boundary region into nonoverlapping parts. Submodular optimization is widely used in machine learning, If the objective function has sub-modularity, it exists a
simple greedy algorithm which can approximate the optimal solution of the problem with constant factor in polynomial time. In this paper,
submodular optimization is introduced into the processing of nodes in overlapping communities. and a community detection algorithm
(SO-CDA) for boundary region processing based on submodular optimization is proposed. The device location function is defined for
submodular optimization, the partition of overlapping nodes is converted to the maximization of submodular function. The experimental
results on seven real networks show that SO-CDA can effectively divide communities and achieve more stable performance. |
| 查看全文 查看/发表评论 下载PDF阅读器 |
|
|
|
