Journal of Computer Applications ›› 2023, Vol. 43 ›› Issue (4): 1109-1114.DOI: 10.11772/j.issn.1001-9081.2022040562
Special Issue: 数据科学与技术
• Data science and technology • Previous Articles Next Articles
Peng LI1,2, Shilin WANG1,2(), Guangwu CHEN1,2, Guanghui YAN3
Received:
2022-04-24
Revised:
2022-08-20
Accepted:
2022-08-30
Online:
2022-10-14
Published:
2023-04-10
Contact:
Shilin WANG
About author:
LI Peng, born in 1985, Ph. D. candidate. His research interests include complex networks, intelligent transportation, information system engineering.Supported by:
通讯作者:
王世林
作者简介:
李鹏(1985—),男,青海海东人,博士研究生,CCF会员,主要研究方向:复杂网络、智能交通、信息系统工程;基金资助:
CLC Number:
Peng LI, Shilin WANG, Guangwu CHEN, Guanghui YAN. Key node mining in complex network based on improved local structural entropy[J]. Journal of Computer Applications, 2023, 43(4): 1109-1114.
李鹏, 王世林, 陈光武, 闫光辉. 基于改进的局部结构熵复杂网络重要节点挖掘[J]. 《计算机应用》唯一官方网站, 2023, 43(4): 1109-1114.
Add to citation manager EndNote|Ris|BibTeX
URL: https://www.joca.cn/EN/10.11772/j.issn.1001-9081.2022040562
节点 | 节点 | ||
---|---|---|---|
1 | 0.04 | 6 | 0.50 |
2 | 0.04 | 7 | 1.43 |
3 | 0.50 | 8 | 0.50 |
4 | 1.35 | 9 | 0.50 |
5 | 1.06 |
Tab. 1 Importance measure for each node in Fig.1(a) by using Eq.(5)
节点 | 节点 | ||
---|---|---|---|
1 | 0.04 | 6 | 0.50 |
2 | 0.04 | 7 | 1.43 |
3 | 0.50 | 8 | 0.50 |
4 | 1.35 | 9 | 0.50 |
5 | 1.06 |
节点 | 节点 | ||
---|---|---|---|
1 | 0.54 | 6 | 0.50 |
2 | 0.54 | 7 | 1.43 |
3 | 0.50 | 8 | 0.50 |
4 | 1.35 | 9 | 0.50 |
5 | 1.06 |
Tab. 2 Importance measure for each node in Fig. 1(a) by using Eq.(7)
节点 | 节点 | ||
---|---|---|---|
1 | 0.54 | 6 | 0.50 |
2 | 0.54 | 7 | 1.43 |
3 | 0.50 | 8 | 0.50 |
4 | 1.35 | 9 | 0.50 |
5 | 1.06 |
网络 | 节点 数量 | 边数量 | 平均度 | 平均 距离 | 平均 聚集系数 |
---|---|---|---|---|---|
Football | 115 | 613 | 10.661 | 2.508 | 0.403 |
Dolphins | 62 | 159 | 5.129 | 3.357 | 0.259 |
1 133 | 5 452 | 9.624 | 3.606 | 0.625 | |
US Airlines | 332 | 2 126 | 12.807 | 2.738 | 0.625 |
western US states grid | 4 941 | 6 954 | 2.669 | 18.989 | 0.080 |
Tab. 3 Statistical characteristics of each real network
网络 | 节点 数量 | 边数量 | 平均度 | 平均 距离 | 平均 聚集系数 |
---|---|---|---|---|---|
Football | 115 | 613 | 10.661 | 2.508 | 0.403 |
Dolphins | 62 | 159 | 5.129 | 3.357 | 0.259 |
1 133 | 5 452 | 9.624 | 3.606 | 0.625 | |
US Airlines | 332 | 2 126 | 12.807 | 2.738 | 0.625 |
western US states grid | 4 941 | 6 954 | 2.669 | 18.989 | 0.080 |
方法 | 排名前10的节点序号 | |||||||||
---|---|---|---|---|---|---|---|---|---|---|
1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | |
PLEA | 14 | 37 | 20 | 45 | 1 | 33 | 51 | 29 | 36 | 17 |
LE | 14 | 45 | 37 | 33 | 20 | 51 | 29 | 57 | 1 | 13 |
DC | 6 | 9 | 13 | 18 | 29 | 45 | 51 | 57 | 30 | 7 |
KS | 14 | 37 | 45 | 33 | 51 | 17 | 20 | 29 | 51 | 1 |
DCL | 36 | 20 | 14 | 37 | 1 | 51 | 17 | 23 | 25 | 29 |
CEN | 36 | 20 | 37 | 14 | 1 | 17 | 45 | 51 | 40 | 50 |
Tab. 4 Top 10 nodes in Dolphins network under different measurement methods
方法 | 排名前10的节点序号 | |||||||||
---|---|---|---|---|---|---|---|---|---|---|
1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | |
PLEA | 14 | 37 | 20 | 45 | 1 | 33 | 51 | 29 | 36 | 17 |
LE | 14 | 45 | 37 | 33 | 20 | 51 | 29 | 57 | 1 | 13 |
DC | 6 | 9 | 13 | 18 | 29 | 45 | 51 | 57 | 30 | 7 |
KS | 14 | 37 | 45 | 33 | 51 | 17 | 20 | 29 | 51 | 1 |
DCL | 36 | 20 | 14 | 37 | 1 | 51 | 17 | 23 | 25 | 29 |
CEN | 36 | 20 | 37 | 14 | 1 | 17 | 45 | 51 | 40 | 50 |
方法 | 排名前10的节点序号 | |||||||||
---|---|---|---|---|---|---|---|---|---|---|
1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | |
PLEA | 82 | 80 | 58 | 69 | 6 | 3 | 15 | 0 | 104 | 5 |
LE | 7 | 15 | 53 | 2 | 67 | 88 | 104 | 1 | 3 | 6 |
DC | 46 | 49 | 67 | 73 | 83 | 110 | 74 | 111 | 60 | 6 |
KS | 0 | 1 | 2 | 3 | 5 | 6 | 7 | 15 | 53 | 67 |
DCL | 58 | 82 | 80 | 63 | 36 | 42 | 69 | 24 | 6 | 43 |
CEN | 82 | 58 | 80 | 69 | 63 | 24 | 6 | 0 | 15 | 36 |
Tab. 5 Top 10 nodes in Football network under different measurement methods
方法 | 排名前10的节点序号 | |||||||||
---|---|---|---|---|---|---|---|---|---|---|
1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | |
PLEA | 82 | 80 | 58 | 69 | 6 | 3 | 15 | 0 | 104 | 5 |
LE | 7 | 15 | 53 | 2 | 67 | 88 | 104 | 1 | 3 | 6 |
DC | 46 | 49 | 67 | 73 | 83 | 110 | 74 | 111 | 60 | 6 |
KS | 0 | 1 | 2 | 3 | 5 | 6 | 7 | 15 | 53 | 67 |
DCL | 58 | 82 | 80 | 63 | 36 | 42 | 69 | 24 | 6 | 43 |
CEN | 82 | 58 | 80 | 69 | 63 | 24 | 6 | 0 | 15 | 36 |
方法 | 排名前10的节点序号 | |||||||||
---|---|---|---|---|---|---|---|---|---|---|
1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | |
PLEA | 2553 | 4458 | 3895 | 4345 | 2382 | 2542 | 2434 | 3468 | 1334 | 2617 |
LE | 2553 | 4458 | 4345 | 3895 | 2542 | 4352 | 4384 | 4381 | 2585 | 4332 |
KS | 4398 | 4332 | 4352 | 4335 | 4344 | 4347 | 4381 | 4384 | 4401 | 4402 |
DC | 2553 | 4458 | 831 | 3468 | 4345 | 2382 | 2542 | 2575 | 2585 | 3895 |
DCL | 4458 | 3468 | 2575 | 831 | 2439 | 2382 | 2553 | 1224 | 2554 | 1334 |
CEN | 4458 | 3468 | 2553 | 831 | 2575 | 2382 | 2439 | 1224 | 2434 | 1005 |
Tab. 6 Top 10 nodes in western US states power under different measurement methods
方法 | 排名前10的节点序号 | |||||||||
---|---|---|---|---|---|---|---|---|---|---|
1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | |
PLEA | 2553 | 4458 | 3895 | 4345 | 2382 | 2542 | 2434 | 3468 | 1334 | 2617 |
LE | 2553 | 4458 | 4345 | 3895 | 2542 | 4352 | 4384 | 4381 | 2585 | 4332 |
KS | 4398 | 4332 | 4352 | 4335 | 4344 | 4347 | 4381 | 4384 | 4401 | 4402 |
DC | 2553 | 4458 | 831 | 3468 | 4345 | 2382 | 2542 | 2575 | 2585 | 3895 |
DCL | 4458 | 3468 | 2575 | 831 | 2439 | 2382 | 2553 | 1224 | 2554 | 1334 |
CEN | 4458 | 3468 | 2553 | 831 | 2575 | 2382 | 2439 | 1224 | 2434 | 1005 |
1 | XU X, ZHU C, WANG Q Y, et al. Identifying vital nodes in complex networks by adjacency information entropy[J]. Scientific Reports, 2020, 10: No.2691. 10.1038/s41598-020-59616-w |
2 | 任晓龙,吕琳媛. 网络重要节点排序方法综述[J]. 科学通报, 2014, 59(13): 1175-1197. 10.1360/972013-1280 |
REN X L, LYU L Y. Review of ranking nodes in complex networks[J]. Chinese Science Bulletin, 2014, 59(13):1175-1197. 10.1360/972013-1280 | |
3 | 任卓明,刘建国,邵凤,等. 复杂网络中最小K-核节点的传播能力分析[J]. 物理学报, 2013, 62(10): No.108902. 10.7498/aps.62.108902 |
REN Z M, LIU J G, SHAO F, et al. Analysis of the spreading influence of the nodes with minimum K-shell value in complex networks[J]. Acta Physica Sinica. 2013, 62(10): No.108902. 10.7498/aps.62.108902 | |
4 | YANG X, XIAO F Y. An improved gravity model to identify influential nodes in complex networks based on k-shell method[J]. Knowledge-Based Systems, 2021, 227: No.107198. 10.1016/j.knosys.2021.107198 |
5 | SHANG Q Y, DENG Y, CHEONG K H. Identifying influential nodes in complex networks: effective distance gravity model[J]. Information Sciences, 2021, 577:162-179. 10.1016/j.ins.2021.01.053 |
6 | ULLAH A, WANG B, SHENG J F, et al. Identifying vital nodes from local and global perspectives in complex networks[J]. Expert Systems with Applications, 2021, 186: No.115778. 10.1016/j.eswa.2021.115778 |
7 | 郭庆来,辛蜀骏,王剑辉,等. 由乌克兰停电事件看信息能源系统综合安全评估[J]. 电力系统自动化, 2016, 40(5): 145-147. 10.7500/AEPS20160113101 |
GUO Q L, XIN S J, WANG J H, et al. Comprehensive security assessment for a cyber physical energy system: a lesson from Ukraine’s blackout[J]. Automation of Electric Power Systems, 2016, 40(5):145-147. 10.7500/AEPS20160113101 | |
8 | 胡钢,徐翔,高浩,等. 基于邻接信息熵的网络节点重要性识别算法[J]. 系统工程理论与实践, 2020, 40(3): 714-725. 10.12011/1000-6788-2018-1805-12 |
HU G, XU X, GAO H, et al. Node importance recognition algorithm based on adjacency information entropy in networks[J]. Systems Engineering — Theory & Practice, 2020, 40(3):714-725. 10.12011/1000-6788-2018-1805-12 | |
9 | ALBERT R, JEONG W, BARABÁSI A L. Diameter of the world-wide web[J]. Nature, 1999, 401(6749): 130-131. 10.1038/43601 |
10 | BRANDES U, BORGATTI S P, FREEMAN L C. Maintaining the duality of closeness and betweenness centrality[J]. Social Networks, 2016, 44:153-159. 10.1016/j.socnet.2015.08.003 |
11 | FREEMAN L C. A set of measures of centrality based on betweenness[J]. Sociometry, 1977, 40(1): 35-41. 10.2307/3033543 |
12 | NEWMAN M E J. Finding community structure in networks using the eigenvectors of matrices[J]. Physical Review. E, Statistical, Nonlinear, and Soft Matter Physics, 2006, 74(3): No.036104. 10.1103/physreve.74.036104 |
13 | BERAHMAND K, BOUYER A, SAMADI N. A new local and multidimensional ranking measure to detect spreaders in social networks[J]. Computing, 2019, 101(11): 1711-1733. 10.1007/s00607-018-0684-8 |
14 | BERAHMAND K, BOUYER A, SAMADI N. A new centrality measure based on the negative and positive effects of clustering coefficient for identifying influential spreaders in complex networks[J]. Chaos, Solitons and Fractals, 2018, 110: 41-54. 10.1016/j.chaos.2018.03.014 |
15 | 马润年,王班,王刚,等. 基于互信息的通信网络节点重要性度量方法[J]. 电子学报, 2017, 45(3): 747-752. 10.3969/j.issn.0372-2112.2017.03.035 |
MA R N, WANG B, WANG G, et al. Evaluation method for node importance in communication network based on mutual information[J]. Acta Electronica Sinica, 2017, 45(3):747-752. 10.3969/j.issn.0372-2112.2017.03.035 | |
16 | FEI L G, DENG Y. A new method to identify influential nodes based on relative entropy[J]. Chaos, Solitons and Fractals, 2017, 104:257-267. 10.1016/j.chaos.2017.08.010 |
17 | ZHANG Q, LI M Z, DU Y X, et al. Local structure entropy of complex networks[EB/OL]. (2014-12-12) [2022-02-11].. |
18 | 吕非非,徐雅斌,李卓,等. 面向微博影响力的社交网络特征分析[J]. 计算机应用, 2013, 33(12):3359-3362, 3418. 10.3724/sp.j.1087.2013.03359 |
LYU F F, XU Y B, LI Z, et al. Analysis of characteristics of social networks in terms of microblog impact[J]. Journal of Computer Applications, 2013, 33(12): 3359-3362, 3418. 10.3724/sp.j.1087.2013.03359 | |
19 | GIRVAN M, NEWMAN M E J. 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. 10.1073/pnas.122653799 |
20 | LUSSEAU D, SCHNEIDER K, BOISSEAU O J, et al. The bottlenose dolphin community of Doubtful Sound features a large proportion of long-lasting associations[J]. Behavioral Ecology and Sociobiology, 2003, 54(4):396-405. 10.1007/s00265-003-0651-y |
21 | GUIMERÀ R, DANON L, DÍAZ-GUILERA A, et al. Self-similar community structure in a network of human interactions[J]. Physical Review. E, Statistical, Nonlinear, and Soft Matter Physics, 2003, 68(6): No.065103. 10.1103/physreve.68.065103 |
22 | WATTS D J, STROGATZ S H. Collective dynamics of ‘small-world’ networks[J]. Nature, 1998, 393(6684): 440-442. 10.1038/30918 |
23 | NEMESURE M D, SCHWEDHELM T M, SACERDOTE S, et al. A measure of local unique-ness to identify linchpins in a social network with node attributes[J]. Applied Network Science, 2021, 6: No.56. 10.1007/s41109-021-00400-8 |
24 | VRAGOVIĆ I, LOUIS E, DÍAZ-GUILERA A. Efficiency of informational transfer in regular and complex networks[J]. Physical Review. E, Statistical, Nonlinear, and Soft Matter Physics, 2005, 71(3): No.036122. 10.1103/physreve.71.036122 |
25 | 任卓明,邵凤,刘建国,等. 基于度与集聚系数的网络节点重要性度量方法研究[J]. 物理学报, 2013, 62(12): No.128901. 10.7498/aps.62.128901 |
REN Z M, SHAO F, LIU J G, et al. Node importance measurement based on the degree and clustering coefficient information[J]. Acta Physica Sinica, 2013, 62(12):No.128901. 10.7498/aps.62.128901 |
[1] | Zhongyu WANG, Xiaodong QIAN. Optimization of edge connection rules for supply chain network based on improved expectation maximization algorithm [J]. Journal of Computer Applications, 2024, 44(11): 3386-3395. |
[2] | Jie HUANG, Ruizi WU, Junli LI. Efficient adaptive robustness optimization algorithm for complex networks [J]. Journal of Computer Applications, 2024, 44(11): 3530-3539. |
[3] | Lin ZHOU, Yuzhi XIAO, Peng LIU, Youpeng QIN. Community mining algorithm based on multi-relationship of nodes and its application [J]. Journal of Computer Applications, 2023, 43(5): 1489-1496. |
[4] | Xiangxi WEN, Yating PENG, Kexin BI, Yuming HENG, Minggong WU. Situation prediction of flight conflict network based on online fuzzy least squares support vector machine with optimal training set [J]. Journal of Computer Applications, 2023, 43(11): 3632-3640. |
[5] | LI Zhanli, LI Ying, LUO Xiangyu, LUO Yingxiao. Local community detection algorithm based on Monte-Carlo iterative solving strategy [J]. Journal of Computer Applications, 2023, 43(1): 104-110. |
[6] | Yuyu MENG, Jing GUO. Link prediction algorithm based on information entropy improved PCA model [J]. Journal of Computer Applications, 2022, 42(9): 2823-2829. |
[7] | Zhigang HAO, Li QIN. Method for discovering important nodes in food safety standard reference network based on multi-attribute comprehensive evaluation [J]. Journal of Computer Applications, 2022, 42(4): 1178-1185. |
[8] | Jun HU, Zhengkang XU, Li LIU, Fujin ZHONG. Network embedding method based on multi-granularity community information [J]. Journal of Computer Applications, 2022, 42(3): 663-670. |
[9] | Guangfu CHEN, Haibo WANG, Yanping LIAN. Link prediction in directed network based on high-order self-included collaborative filtering [J]. Journal of Computer Applications, 2022, 42(10): 3060-3068. |
[10] | CAI Biao, LI Ruicen, WU Yuanyuan. Impact and enhancement of similarity features on link prediction [J]. Journal of Computer Applications, 2021, 41(9): 2569-2577. |
[11] | LI Yafang, LIANG Ye, FENG Weiwei, ZU Baokai, KANG Yujian. Deep network embedding method based on community optimization [J]. Journal of Computer Applications, 2021, 41(7): 1956-1963. |
[12] | LI Ping, WANG Fen, CHEN Qidong, SUN Jun. Discrete random drift particle swarm optimization algorithm for solving multi-objective community detection problem [J]. Journal of Computer Applications, 2021, 41(3): 803-811. |
[13] | ZHENG Wenping, YUE Xiangdou, YANG Gui. Improved label propagation algorithm based on random walk [J]. Journal of Computer Applications, 2020, 40(12): 3423-3429. |
[14] | CHENG Qiwei, CHEN Qimai, HE Chaobo, LIU Hai. Overlapping community detection method based on improved symmetric binary nonnegative matrix factorization [J]. Journal of Computer Applications, 2020, 40(11): 3203-3210. |
[15] | LIU Yuyang, LI Longjie, SHAN Na, CHEN Xiaoyun. Link prediction method fusing clustering coefficients [J]. Journal of Computer Applications, 2020, 40(1): 28-35. |
Viewed | ||||||
Full text |
|
|||||
Abstract |
|
|||||