基于子模优化的边界域处理社团发现算法
DOI:
CSTR:
作者:
作者单位:

作者简介:

通讯作者:

中图分类号:

TP181;TN99

基金项目:

国家自然科学基金(61673020,61602003)、安徽省自然科学基金 (1708085QF156)、安徽省高校优秀青年人才项目( gxyq2019068)、电子信息系统仿真设计安徽省重点实验室开放基金(2019ZDSYSZY06)资助项目


Community detection algorithm for boundary region processing based on submodular optimization
Author:
Affiliation:

Fund Project:

  • 摘要
  • |
  • 图/表
  • |
  • 访问统计
  • |
  • 参考文献
  • |
  • 相似文献
  • |
  • 引证文献
  • |
  • 资源附件
  • |
  • 文章评论
    摘要:

    使用聚类粒化方法求取非重叠社团结构时,经常会出现重叠区域。 三支决策模型将两个存在重叠的社团的左边社团中 非重叠部分定义为正域,右边社团中非重叠部分定义为负域,而两个社团的重叠部分定义为边界域。 为了获得更好的社团性 能,须将边界域中的节点进行二次划分。 子模优化在机器学习中有广泛的应用,如果目标函数具有子模性,则存在一个简单的 贪心算法能在多项式时间内以常数因子逼近问题的最优解。 将子模优化思想引入社团重叠区域节点的处理,提出一种基于子 模优化的边界域处理社团发现算法(SO-CDA)。 定义设备选址函数进行子模优化,重叠节点的划分可以转化为子模函数最大 化问题,在 7 个真实网络上的实验结果表明,SO-CDA 能够有效地进行社团划分,性能更加稳定。

    Abstract:

    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.

    参考文献
    相似文献
    引证文献
引用本文

杨雪洁,曹风云,陈 洁,赵 姝,张燕平.基于子模优化的边界域处理社团发现算法[J].电子测量与仪器学报,2020,34(4):111-117

复制
分享
文章指标
  • 点击次数:
  • 下载次数:
  • HTML阅读次数:
  • 引用次数:
历史
  • 收稿日期:
  • 最后修改日期:
  • 录用日期:
  • 在线发布日期: 2023-06-15
  • 出版日期:
文章二维码