基于标记注意力机制的社区发现算法

doi:10.6040/j.issn.1671-9352.7.2021.097

摘要/Abstract

摘要： 针对网络的聚类进行研究,提出了一种基于标记注意力机制的社区发现算法,网络特征通过标记节点频率及反示例节点频率联合度量,为使网络特征的度量更加关注于示例节点的细节信息,引入注意力机制来处理网络特征。社区划分由复杂网络预处理、网络节点的策略、社区博弈归并三个部分组成,其中网络节点的策略由无贡献节点归并、节点到社区的判断以及节点逻辑标记和的判断三个步骤组成。实验借助于真实网络进行验证,在归一化互信息、模块度、社区划分数量及运行时间四个方面,基于标记注意力机制的社区发现算法都优于其它社区发现算法。在实际生活中应用此算法,能够更加直观地显示网络内部之间存在的联系。

关键词: 复杂网络, 标记节点频率, 反示例节点频率, 注意力机制, 社区发现

Abstract: For network clustering, this paper proposes a community discovery algorithm based on label attention mechanism. Network features are jointly measured by label node frequency and inverse example node frequency, and attention mechanism is introduced to handle network features in order to make the metric of network features more focused on the detailed information of example nodes. Community division is composed of three parts: complex network preprocessing, network node strategy, and community game merging. The network nodes strategy is consists of three steps: the non-contributing node merging, the judgment of the node to the community and the judgment of the degree of the node. The experiments are verified with the help of real networks. The results show that the community discovery algorithm based on label attention mechanism outperforms other community discovery algorithms in four aspects: normalized mutual information, modularity, number of community divisions and running time. Applying this algorithm in real life can more intuitively show the existing connections within the network.

Key words: complex network, label node frequency, the inverse example node frequency, attention mechanism, community discovery

中图分类号:

TP391

王静红,梁丽娜,李昊康,王熙照. 基于标记注意力机制的社区发现算法[J]. 《山东大学学报(理学版)》, 2022, 57(12): 1-12.

WANG Jing-hong, LIANG Li-na, LI Hao-kang, WANG Xi-zhao. Community discovery algorithm based on label attention mechanism[J]. JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE), 2022, 57(12): 1-12.

参考文献

[1] 王静红,梁丽娜,李昊康,等.基于注意力网络特征的社区发现算法[J]. 山东大学学报(理学版), 2021, 56(9):1-12, 20. WANG Jinghong, LIANG Lina, LI Haokang, et al. Community discovery algorithm based on attention network feature[J]. Journal of Shandong University(Natural Science), 2021, 56(9):1-12,20.
[2] YANG Haijuan, CHENG Jianjun, YANG Zeyi, et al. A node similarity and community link strength-based community discovery algorithm[J]. Complexity, 2021, 2021(22):1-17.
[3] SINGHAL A, CAO S, CHURAS C, et al. Multiscale community detection in cytoscape[J]. PLoS Computational Biology, 2020, 16(10): e1008239.
[4] LI T, LEVINA E, ZHU J. Network cross-validation by edge sampling[J]. Biometrika, 2020, 107(2):257-276.
[5] RANGARAJAN N, KULKARNI P, HANNENHALLI S. Evolutionarily conserved network properties of intrinsically disordered proteins[J]. Plos One, 2015, 10(5):1-16.
[6] CHOOBDAR S, AHSEN M E, CRAWFORD J, et al. Assessment of network module identification across complex diseases[J]. Nature Methods, 2019, 16(9):843-852.
[7] CHEN P, REDNER R. Community structure of the physical review citation network[J]. Journal of Informetrics, 2010, 4(3):278-290.
[8] CHUNAEV P. Community detection in node-attributed social networks: a survey[J]. Computer Science Review, 2020, 37:100286.
[9] CHENG Ziwei, ZENG Ziwei. Joint label-specific features and label correlation for multi-label learning with missing label[J]. Applied Intelligence, 2020, 50(11):4029-4049.
[10] CHEN J, LI Y, YANG X, et al. VGHC: a variable granularity hierarchical clustering for community detection[J]. Granular Computing, 2021, 6(1):1-10.
[11] WU Zhaole, WANG Xin, FANG Wenyi, et al. Community detection based on first passage probabilities[J]. Physics Letters A, 2021, 390:127099.
[12] LIU Xiaoyang, DING Nan, LIU Chao, et al. Novel social network community discovery method combined local distance with node rank optimization function[J]. Applied Intelligence, 2021, 51(7):4788-4805.
[13] AKIMUSHKIN C, AMANCIO D R, OLIVEIRA O N. Text authorship identified using the dynamics of word co-occurrence networks[J]. Plos One, 2017, 12(1):1-15.
[14] SHI C, HU B B, ZHAO W X, et al. Heterogeneous information network embedding for recommendation[J]. IEEE Transactions on Knowledge and Data Engineering, 2018, 31(2):357-370.
[15] LI Yongjun, SU Zhaoting, YANG Jiaqi, et al. Exploiting similarities of user friendship networks across social networks for user identification[J]. Information Sciences, 2020, 506:78-98.
[16] WANG Shanfeng, GONG Maoguo, LIU Wenfeng, et al. Preventing epidemic spreading in networks by community detection and memetic algorithm[J]. Applied Soft Computing, 2020, 89:106118.
[17] HU Baofang, WANG Hong, ZHENG Yuanjie. Sign prediction and community detection in directed signed networks based on random walk theory[J]. International Journal of Embedded Systems, 2019, 11(2):200-209.
[18] NEWMAN M E J. The structure and function of complex networks[J]. SIAM Review, 2003, 45(2):167-256.
[19] GUO Kun, HE Ling, CHEN Yuzhong, et al. A local community detection algorithm based on internal force between nodes[J]. Applied Intelligence, 2020, 50(2):328-340.
[20] YANG Gui, ZHENG Wenping, CHE Chenhao, et al. Graph-based label propagation algorithm for community detection[J]. International Journal of Machine Learning and Cybernetics, 2020, 11(6):1319-1329.
[21] WEN Xuyun, LIN Ying. A multi-objective community detection algorithm for directed network based on random walk[J]. IEEE Access, 2019, 7:162652-162663.
[22] HUANG Jin, ZHANG Tinghua, YU Weihao, et al. Community detection based on modularized deep nonnegative matrix factorization[J]. International Journal of Pattern Recognition and Artificial Intelligence, 2021, 35(2):2159006.
[23] SHI P, HE K, BINDEL D, et al. Locally-biased spectral approximation for community detection[J]. Knowledge-Based Systems, 2019, 164:459-472.
[24] CHU Junfeng, WANG Yingming, LIU Xinwang, et al. Social network community analysis based large-scale group decision making approach with incomplete fuzzy preference relations[J]. Information Fusion, 2020, 60:98-120.
[25] WU Zonghan, PAN Shirui, CHEN Fengwen, et al. A comprehensive survey on graph neural networks[J]. IEEE Transactions on Neural Networks and Learning Systems, 2020, 32(1):4-24.
[26] ARASTEH M, ALIZADEH S. A fast divisive community detection algorithm based on edge degree betweenness centrality[J]. Applied Intelligence, 2019, 49(2):689-702.
[27] 付常雷. 一种基于Newman快速算法改进的社团划分算法[J]. 计算机技术与发展, 2018, 28(1):33-35. FU Changlei. A community partitioning algorithm based on improved fast-Newman algorithm[J]. Computer Technology and Development, 2018, 28(1):33-35.
[28] GIRVAN M, NEWMAN M E. Community structure in social and biological networks[J]. Proceedings of the National Academy of Sciences of the United States of America, 2002, 99(12):7821-7826.
[29] LIU Hongtao, FEN Linghu, JIAN Jie, et al. Overlapping community discovery algorithm based on hierarchical agglomerative clustering[J]. International Journal of Pattern Recognition and Artificial Intelligence, 2018, 32(3):1850008.
[30] YUAN Chao, RONG Chuitian, YAO Qingshuang. Boundary-connection deletion strategy based method for community detection in complex networks[J]. Applied Intelligence, 2020, 50(11):3570-3589.
[31] NEWMAN M E J. Finding community structure in networks using the eigenvectors of matrices[J]. Physical Review E, 2006, 74(3):036104.
[32] ZACHARY W W. An information flow model for conflict and fission in small groups[J]. Journal of Anthropological Research, 1977, 33(4):452-473.
[33] LV Lintao, WU Jialin, LV Hui. A community discovery algorithm for complex networks[J]. Journal of Physics Conference Series, 2020, 1533(3):032076.
[34] XIE Yu, GONG Maoguo, WANG Shanfeng, et al. Community discovery in networks with deep sparse filtering[J]. Pattern Recognition, 2018, 81:50-59.
[35] HE Chaobo, FEI Xiang, LI Hanchao, et al. Improving NMF-based community discovery using distributed robust nonnegative matrix factorization with simrank similarity measure[J]. The Journal of Supercomputing, 2018, 74(10):5601-5624.

多维度评价

Viewed

Full text

Abstract

Cited

Shared

Discussed