融入节点和边缘重要性分析的社区发现算法

Community Detection Algorithm Base on Node and Edge Analysis

【目的】分析网络中节点和边缘的重要性,提升基于目标函数优化的社区发现算法的性能。【方法】依据三角结构计算节点重要性,删减节点构建核心网络;依据三角结构计算边缘重要性,引入加权模块度指标,从局部视角制定算法优化指标,实现核心网络社区发现;基于此扩展得到原始网络的真实社区结构。【结果】在一系列合成网络和4个真实网络数据集上的实验表明,本文算法相较于6种对比算法,整体性能在平均F1分数指标上提升19.85个百分点,在稠密网络上优势更加明显。【局限】算法的执行需要预先给定一个参数的取值。【结论】本文算法同时实现了非重叠和重叠社区发现,能提高社区发现的有效性和效率。

[Objective]This paper analyzes the importance of network nodes and edges,aiming to improve the performance of community detection algorithms based on objective function optimization.[Methods]First,we measured the importance of nodes based on the triangular structure and constructed a core network by deleting some nodes.Second,we measured the importance of edges based on the triangular structure.Then,we optimized the algorithm with the weighted modularity metric from a local perspective to detect communities in the core network.Finally,we extended these communities to obtain the actual community structure of the original network.[Results]We examined the proposed algorithm on a series of synthetic networks and four real-world network datasets.Our new algorithm’s F1 value was 19.85%higher than the baseline models.It yielded better results on dense networks.[Limitations]The proposed algorithm needs a user-specified parameter.[Conclusions]The proposed algorithm could effectively identify the non-overlapping and overlapping network communities.