您的位置：山东大学 -> 科技期刊社 -> 《山东大学学报（理学版）》

《山东大学学报(理学版)》 ›› 2021, Vol. 56 ›› Issue (9): 1-12,20.doi: 10.6040/j.issn.1671-9352.4.2021.174

•   •    下一篇

基于注意力网络特征的社区发现算法

王静红1,2(),梁丽娜1,李昊康1,周易3,*()   

  1. 1. 河北师范大学计算机与网络空间安全学院, 河北 石家庄 050024
    2. 河北省供应链大数据分析与数据安全工程研究中心, 河北 石家庄 050024
    3. 上海海关科技处, 上海 200002
  • 收稿日期:2021-06-02 出版日期:2021-09-20 发布日期:2021-09-13
  • 通讯作者: 周易 E-mail:wangjinghong@126.com;zhouwangyilang@126.com
  • 作者简介:王静红(1967—), 女, 博士, 教授, 研究方向为人工智能、大数据与数据挖掘、模式识别等. E-mail: wangjinghong@126.com
  • 基金资助:
    河北省自然科学基金资助项目(F2019205303);河北省引进留学人员资助项目(C20200340)

Community discovery algorithm based on attention network feature

Jing-hong WANG1,2(),Li-na LIANG1,Hao-kang LI1,Yi ZHOU3,*()   

  1. 1. School of Computer and Cyber Security, Hebei Normal University, Shijiazhuang 050024, Hebei, China
    2. Hebei Provincial Engineering Research Center for Supply Chain Big Data Analytics & Data Security, Shijiazhuang 050024, Hebei, China
    3. Science & Technology Division, Shanghai Customs District P R China, Shanghai 200002, China
  • Received:2021-06-02 Online:2021-09-20 Published:2021-09-13
  • Contact: Yi ZHOU E-mail:wangjinghong@126.com;zhouwangyilang@126.com

RichHTML

122

PDF (PC)

296

摘要：

现实世界中许多网络都是根据社区结构紧密组织起来的, 发现社区对于了解复杂网络的结构及其关系有很大的帮助, 文中提出了一种基于注意力网络特征的社区发现(community discovery algorithm based on attention network features, CANF)算法, 利用标记节点频率和反示例节点频率度量初始网络标记特征, 并且引入注意力机制, 对示例节点的每个邻居节点更好地分配权重, 将初始权重与分配权重相结合, 使初始度量的网络特征获取更多与目标有关的细节信息。文中通过分配的注意力网络特征进行复杂网络预处理以及社区博弈归并, 于真实网络中进行验证, 实验结果表明, CANF算法在准确度、模块度以及运行时间方面优于其他社区发现算法。

关键词: 复杂网络, 注意力网络特征, 社区发现, 网络预处理, 社区博弈归并

Abstract:

In the real world, many networks are closely organized according to the community structure. It has been found that the community is of great help in understanding the structure and relationship of complex networks. This paper proposes a community discovery algorithm based on attention network features (CANF algorithm). It uses the label node frequency and the inverse example node frequency to measure the initial network label characteristics, and introduces the attention mechanism, and updates each neighbor node of the example node. Combined the initial weight with the assigned weight, the network features of the initial measure can obtain more detailed information related to the target. In this paper, complex network preprocessing and community game merge are carried out through distributed attention network features. The experimental results show that the accuracy, modularity and running time of the community discovery algorithm based on attention network features are better than other community discovery algorithms.

Key words: complex network, attention network feature, community discovery, network preprocessing, community game merge

中图分类号: 

  • TP391

图1

注意力网络特征"

图2

CANF算法模型框架"

表1

实验数据集信息"

数据集信息真实网络数据集
karate dolphin lesmis football polbooks adjnoun netscience
节点数量 34 62 77 115 105 112 1589
边数量 78 159 508 613 441 425 2742

图3

CANF算法在空手道俱乐部网络上划分的社区图"

图4

空手道俱乐部网络的自然划分社区图"

表2

CANF算法与其他算法在真实网络上的NMI"

数据集 CANF算法 GN算法 Fast-Newman算法 SLPA
karate 0.838 0.652 0.621 0.414
dolphin 0.814 0.554 0.814 0.560

表3

LPA算法在真实网络上的NMI"

数据集迭代次数
1 2 3
karate 0.700 1 6.4229E-16
dolphin 0.513 0.649 1

图5

CANF算法与其他算法在真实网络上的NMI对比"

图6

CANF算法在海豚网络上划分的社区图"

表4

CANF算法与其他算法在各真实网络数据集中的模块度Q"

数据集 CANF算法 GN算法 LPA Fast-Newman算法 SLPA
karate 0.360 0.263 0.372 0.253 0.068
dolphin 0.380 0.484 0.379 0.450 0.230
lesmis 0.398 0.448 0.317 0.394 0.154
polbooks 0.187 0.312 0.444 0.172 0.264
adjnoun 0.208 0.136 4.046e-17 0.243 0.102

图7

CANF算法与其他算法在各数据集上的模块度Q对比图"

图8

CANF算法在形容词和名词邻接网络上划分的社区图"

表5

CANF算法与其他算法在各数据集上的社区数量"

算法 karate dolphin lesmis football polbooks adjnoun netscience
CANF算法 2 2 3 7 3 4 50
GN算法 2 2 4 12 3 9 406
Fast-Newman算法 12 1 4 5 79 9 200
SLPA 3 7 5 9 8 4 349

表6

N次迭代后LPA在各数据集上的社区数量"

迭代次数 karate dolphin lesmis football polbooks adjnoun
1 2 2 3 12 4 1
2 3 3 4 10 1 1
3 4 4 3 9 3 1
4 1 5 4 11 2 1
5 — — 2 7 — 1
6 — — 3 8 — 1

表7

CANF算法与其他算法在各真实网络上的运行时间"

karate dolphin lesmis football polbooks adjnoun netscience
CANF算法 0.124 0.306 0.309 0.876 0.741 0.487 173.282
GN算法 6.374 45.981 126.757 888.326 513.892 668.046 3.024E+05
LPA 0.066 0.083 0.154 0.190 0.103 0.121 50865.300
Fast-Newman算法 0.389 1.594 9.805 9.312 7.114 8.386 9335.170
SLPA 0.860 1.585 7.718 5.956 3.583 3.649 23.364

图9

CANF算法与其他算法在各真实网络上的运行时间对比图"

1 JI Mengyu , PENG Gaoliang , HE Jun , et al. A two-stage, intelligent bearing-fault-diagnosis method using order-tracking and a one-dimensional convolutional neural network with variable speeds[J]. Sensors, 2021, 21 (3): 675.
doi: 10.3390/s21030675
2 TANG Fengqin , DING Wenwen . Community detection with structural and attribute similarities[J]. Journal of Statistical Computation and Simulation, 2019, 89 (4): 668- 685.
doi: 10.1080/00949655.2019.1568435
3 LI Meizi , LU Shuyi , ZHANG Lele , et al. A community detection method for social network based on community embedding[J]. IEEE Transactions on Computational Social Systems, 2021, 8 (2): 308- 318.
doi: 10.1109/TCSS.2021.3050397
4 DING Yu , WEI Hao , HU Guyu , et al. Unifying community detection and network embedding in attributed networks[J]. Knowledge and Information Systems, 2021, 63 (5): 1221- 1239.
doi: 10.1007/s10115-021-01557-5
5 ZHOU Wenjie , WANG Xingyuan , ZHANG Chuan , et al. Community detection by enhancing community structure in bipartite networks[J]. Modern Physics Letters B, 2019, 33 (7): 1950076.
doi: 10.1142/S0217984919500763
6 GENG Xin . Label distribution learning[J]. IEEE Transactions on Knowledge and Data Engineering, 2016, 28 (7): 1734- 1748.
doi: 10.1109/TKDE.2016.2545658
7 CHEN Qiuji , PENG Yi , CAI Wenting , et al. Research on Chinese aviation network community structure based on Newman fast algorithm[J]. Aeronautical Computing Technique, 2019, 49 (4): 100- 104.
8 毛伊敏, 刘银萍, 梁田, 等. 基于模糊谱聚类的不确定蛋白质相互作用网络功能模块挖掘[J]. 计算机应用, 2019, 39 (4): 104- 112.
MAO Yimin , LIU Yinping , LIANG Tian , et al. Functional module mining in uncertain protein-protein interaction network based on fuzzy spectral clustering[J]. Journal of Computer Applications, 2019, 39 (4): 104- 112.
9 董明刚, 弓佳明, 敬超. 基于谱聚类的多目标进化社区发现算法研究[J]. 计算机科学, 2020, 47 (z1): 461- 466.
DONG Minggang , GONG Jiaming , JING Chao . Multi-objective evolutionary algorithm based on community detection spectral clustering[J]. Computer Science, 2020, 47 (z1): 461- 466.
10 HU Junjie , WANG Zhanquan , CHEN Jiequan . A community partitioning algorithm based on network enhancement[J]. Connection Science, 2021, 33 (1): 42- 61.
doi: 10.1080/09540091.2020.1753172
11 赵卫绩, 张凤斌, 刘井莲. 复杂网络社区发现研究进展[J]. 计算机科学, 2020, 47 (2): 10- 20.
ZHAO Weiji , ZHANG Fengbin , LIU Jinglian . Review on community detection in complex networks[J]. Computer Science, 2020, 47 (2): 10- 20.
12 WANG Jinghong , YANG Jiateng , HE Yichao . Research on semi-supervised community discovery algorithm based on new annealing[J]. The Journal of Engineering, 2020, 2020 (12): 1149- 1154.
doi: 10.1049/joe.2019.1186
13 王静红, 冯婵, 柴变芳. 混合模型下的雅可比矩阵退火算法优化[J]. 深圳大学学报(理工版), 2021, 38 (2): 188- 193.
WANG Jinghong , FENG Chan , CHAI Bianfang . Optimization of Jacobian matrix annealing algorithm based on hybrid model[J]. Journal of Shenzhen University (Science and Engineering), 2021, 38 (2): 188- 193.
14 BOUHMALA Noureddine . A Kernighan-Lin inspired algorithm for max-sat[J]. Science China(Information Sciences), 2019, 62 (11): 206- 208.
15 ARASTEH M , ALIZADEH S . A fast divisive community detection algorithm based on edge degree betweenness centrality[J]. Applied Intelligence, 2018, 49, 1- 14.
16 YANG Haijuan , CHENG Jianjun , YANG Zeyi , et al. A node similarity and community link strength-based community discovery algorithm[J]. Complexity, 2021, 22, 1- 17.
17 SHANG Changpei , DU Jiangen . Research on light weight optimization method of flexible modular family based on least squares regression model[J]. Machine Tool & Hydraulics, 2019, 47 (15): 184- 188.
18 付常雷. 一种基于Newman快速算法改进的社团划分算法[J]. 计算机技术与发展, 2018, 28 (1): 33- 35.
doi: 10.3969/j.issn.1673-629X.2018.01.007
FU Changlei . A community partitioning algorithm based on improved fast-Newman algorithm[J]. Computer Technology and Development, 2018, 28 (1): 33- 35.
doi: 10.3969/j.issn.1673-629X.2018.01.007
19 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.
doi: 10.1007/s13042-019-01042-0
20 SHI Wenhua , NI Yongjing , ZHANG Xiongwei , et al. Deep neural network based monaural speech enhancement with sparse non-negative matrix factorization[J]. Journal of Computer Research and Development, 2018, 55 (11): 2430- 2438.
21 WU Z , PAN S , CHEN F , et al. A comprehensive survey on graph neural networks[J]. IEEE Transactions on Neural Networks and Learning Systems, 2021, 32 (1): 4- 24.
doi: 10.1109/TNNLS.2020.2978386
22 HAQ N F , MORADI M , WANG Z J . Community structure detection from networks with weighted modularity[J]. Pattern Recognition Letters, 2019, 122, 14- 22.
doi: 10.1016/j.patrec.2019.02.005
23 FEI Rong , SHA Jingyuan , XU Qingzheng , et al. A new deep sparse autoencoder for community detection in complex networks[J]. EURASIP Journal on Wireless Communications and Networking, 2020, 2020 (1): 1- 25.
doi: 10.1186/s13638-019-1618-7
24 ACHARYA D B , ZHANG H . Community detection clustering via gumbel softmax[J]. SN Computer Science, 2020, 1 (5): 1- 11.
doi: 10.1007/s42979-020-00264-2
25 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.
doi: 10.1007/s10489-020-02040-4
26 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.
doi: 10.1007/s10489-020-01762-9
27 SHIRJINI M F , FARZI S , NIKANJAM A . MDPCluster: a swarm-based community detection algorithm in large-scale graphs[J]. Computing, 2020, 102 (4): 893- 922.
doi: 10.1007/s00607-019-00787-4
28 NATH Keshab , ROY Swarup . Detecting intrinsic communities in evolving networks[J]. Social Network Analysis and Mining, 2019,
29 LI Wenquan , KANG Qinma , KONG Hanzhang , et al. A novel iterated greedy algorithm for detecting communities in complex network[J]. Social Network Analysis and Mining, 2020, 10 (1): 409- 418.
doi: 10.1007/s13278-020-00641-y
30 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.
doi: 10.1007/s11227-018-2500-9
[1] 张一鸣,王国胤,胡军,傅顺. 基于密度峰值和网络嵌入的重叠社区发现[J]. 《山东大学学报(理学版)》, 2021, 56(1): 91-102.
[2] 张军,李竞飞,张瑞,阮兴茂,张烁. 基于网络有效阻抗的社区发现算法[J]. 山东大学学报（理学版）, 2018, 53(3): 24-29.
[3] 魏思敏,张宪华,张祯,孟庆春,张夏然. 基于复杂网络的虚拟品牌社区意见领袖识别研究——以魅族Flyme社区为例[J]. 《山东大学学报(理学版)》, 2018, 53(11): 26-34.
[4] 王鑫,左万利,朱枫彤,王英. 基于重要结点的社区发现算法[J]. 山东大学学报 (理学版), 2018, 53(11): 67-77.
[5] 王亚奇,王静. 考虑好奇心理机制的动态复杂网络谣言传播研究[J]. 山东大学学报（理学版）, 2017, 52(6): 99-104.
[6] 吴平杰,周斌,吴泉源. COT:一种连续时间序列建模的社区发现算法[J]. 山东大学学报（理学版）, 2016, 51(11): 41-49.
[7] 孙松涛, 何炎祥, 蔡瑞, 李飞, 贺飞艳. 面向微博情感评测任务的多方法对比研究[J]. 山东大学学报（理学版）, 2014, 49(11): 43-50.
Viewed
Full text


Abstract

Cited
  Shared   
  Discussed   
[1] 刘汝军,曹玉霞,周 平 . 利用小反馈实现离散非线性混沌系统的反控制[J]. J4, 2007, 42(7): 30 -32 .
[2] 许万银. 一类拟线性Neumann问题的多重解[J]. J4, 2009, 44(10): 39 -42 .
[3] 杜瑞颖, 杨勇, 陈晶, 王持恒. 一种基于相似度的高效网络流量识别方案[J]. 山东大学学报（理学版）, 2014, 49(09): 109 -114 .
[4] 石长光 . Faddeev模型中的多孤立子解[J]. J4, 2007, 42(7): 38 -40 .
[5] 董炯,曹小红. 算子立方的Weyl定理及其紧摄动[J]. 山东大学学报（理学版）, 2016, 51(8): 15 -21 .
[6] . 银杏叶提取物中总黄酮含量的分析方法研究[J]. J4, 2009, 44(5): 40 -44 .
[7] 张凤霞1，李莹1,2，郭文彬1，赵建立1. 分块Hermite阵与斜Hermite阵的最大秩与最小秩[J]. J4, 2010, 45(4): 106 -110 .
[8] 毕晓冬 . 左拟正规带的自由积[J]. J4, 2008, 43(6): 83 -86 .
[9] 凌密然, 米据生, 马丽. 异构形式背景上的不确定推理[J]. 山东大学学报（理学版）, 2014, 49(08): 28 -32 .
[10] 吴松丽1,2,陈桂友3*. 外-扰动与属性合取收缩规律挖掘-分离[J]. 山东大学学报（理学版）, 2014, 49(06): 1 -5 .
版权所有 © 2018 《山东大学学报(理学版)》编辑部　
地址: 山东省济南市山大南路27号山东大学中心校区（250100）　电话: +86-0531-88366917　E-mail: xblxb@sdu.edu.cn
本系统由北京玛格泰克科技发展有限公司设计开发