JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE) ›› 2021, Vol. 56 ›› Issue (9): 1-12,20.doi: 10.6040/j.issn.1671-9352.4.2021.174

    Next Articles

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

126

PDF (PC)

405

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

CLC Number: 

  • TP391

Fig.1

Attentional network feature"

Fig.2

CANF algorithm model framework"

Table 1

Experimental dataset information"

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

Fig.3

CANF algorithm divides community map in karate club network"

Fig.4

Natural division of karate club network community map[30]"

Table 2

NMI of CANF algorithm and other algorithms on real networks"

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

Table 3

NMI of LPA algorithm on real network"

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

Fig.5

NMI comparison graph of CANF algorithm and other algorithms on real networks"

Fig.6

CANF algorithm divides community map in dolphin network"

Table 4

Modularity Q of CANF algorithm and other algorithms on each real network"

数据集 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

Fig.7

Comparison chart of modularity Q between CANF algorithm and other algorithms on real networks"

Fig.8

CANF algorithm divides community map in polbook network"

Table 5

Number of communities for CANF algorithm and other algorithms on each real network"

算法 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

Table 6

Number of communities after LPA algorithm is executed N times on real networks"

迭代次数 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

Table 7

Running times of the CANF algorithm and other algorithms on each real network  s"

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

Fig.9

Running time comparison figure for CANF algorithm and other algorithms on real networks"

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] Yi-ming ZHANG,Guo-yin WANG,Jun HU,Shun FU. Overlapping community detection based on density peaks and network embedding [J]. JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE), 2021, 56(1): 91-102.
[2] Si-min WEI,Xian-hua ZHANG,Zhen ZHANG,Qing-chun MENG,Xia-ran ZHANG. Virtual brand community opinion leader recognition based on complex network——example of the Meizu Flyme community [J]. JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE), 2018, 53(11): 26-34.
[3] WANG Xin, ZUO Wan-li, ZHU Feng-tong, WANG Ying. Important-node-based community detection algorithm [J]. JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE), 2018, 53(11): 67-77.
[4] WU Ping-jie, ZHOU Bin, WU Quan-yuan. COT: acontinuous temporal modeling algorithm for community discovery [J]. JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE), 2016, 51(11): 41-49.
[5] SUN Song-tao, HE Yan-xiang, CAI Rui, LI Fei, HE Fei-yan. Comparative study of methods for Micro-blog sentiment evaluation tasks [J]. JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE), 2014, 49(11): 43-50.
Viewed
Full text


Abstract

Cited
  Shared   
  Discussed   
[1] LIU Ru-jun,CAO Yu-xia,ZHOU Ping . Anti-control for discrete chaos systems by small feedback[J]. J4, 2007, 42(7): 30 -32 .
[2] HU Mo-Yin. Multiplicity results for a class of quasi-linear Neumann problems[J]. J4, 2009, 44(10): 39 -42 .
[3] DU Rui-ying, YANG Yong, CHEN Jing, WANG Chi-heng. An efficient network traffic classification scheme based on similarity[J]. JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE), 2014, 49(09): 109 -114 .
[4] SHI Chang-guang . Multi-soliton solution of the Faddeev model[J]. J4, 2007, 42(7): 38 -40 .
[5] DONG Jiong, CAO Xiao-hong. Weyls theorem for the cube of operator and compact perturbations[J]. JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE), 2016, 51(8): 15 -21 .
[6] . Study on the determination method of total flavonoids in ginkgo biloba extract[J]. J4, 2009, 44(5): 40 -44 .
[7] ZHANG Fengxia1,　LI Ying1,2,　GUO Wenbin1, ZHAO Jianli1. Extremal ranks for block Hermitian and skew-Hermitian matrices[J]. J4, 2010, 45(4): 106 -110 .
[8] BI Xiao-dong . Free product of left quasi-normal bands[J]. J4, 2008, 43(6): 83 -86 .
[9] LING Mi-ran, MI Ju-sheng, MA Li. Heterogeneous formal contexts for uncertainty reasoning[J]. JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE), 2014, 49(08): 28 -32 .
[10] WU Song-li1,2, CHEN Gui-you3*. Outer-disturbances and attributes conjunctive shrink#br# law mining and separating[J]. JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE), 2014, 49(06): 1 -5 .
Copyright 2018 © Editorial office of JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE)
Supported by Beijing Magtech Co.Ltd