Link Prediction Method Fusion with Local Structural Entropy for Directed Network

LIU Shuxin; CHEN Hongchang; WU Lan; WANG Kai; LI Xing

doi:10.23919/cje.2022.00.166

Volume 33 Issue 1

Jan. 2024

Turn off MathJax

Article Contents

Article Navigation > Chinese Journal of Electronics > 2024 > 33(1): 204-216

Shuxin LIU, Hongchang CHEN, Lan WU, et al., “Link Prediction Method Fusion with Local Structural Entropy for Directed Network,” Chinese Journal of Electronics, vol. 33, no. 1, pp. 204–216, 2024 doi: 10.23919/cje.2022.00.166

Citation:

Shuxin LIU, Hongchang CHEN, Lan WU, et al., “Link Prediction Method Fusion with Local Structural Entropy for Directed Network,” Chinese Journal of Electronics, vol. 33, no. 1, pp. 204–216, 2024 doi: 10.23919/cje.2022.00.166

Citation:

PDF( 3699 KB)

Link Prediction Method Fusion with Local Structural Entropy for Directed Network

doi: 10.23919/cje.2022.00.166

1.
People’s Liberation Army Strategic Support Force Information Engineering University, Zhengzhou 450002, China

More Information

Author Bio:
Shuxin LIU was born in 1987. He received the B.E. degree in communication engineering from Information Engineering University of PLA, Zhengzhou, China, in 2009 and the M.S. and Ph.D. degrees in National Digital Switching System Engineering & Technological R&D Center (NDSC), Zhengzhou, in 2012 and 2016. He is currently a Assistant Research Fellow of NDSC, and he is also the director of the Laboratory of Network Architecture and Signaling Protocol Analysis. His research interests include network evolution, link prediction, network behavior analysis and communication network security. (Email: liushuxin11@126.com)

Hongchang CHEN was born in 1964. He received the B.E. degree in computer application from Zhengzhou University, Zhengzhou, China, in 1986, and the the M.S. degrees in Information Engineering University of PLA, Zhengzhou, in 1989. He is currently a Professor of NDSC, central plains scholar of Henan Province, and the chairman of Henan informatization expert advisory committee. He is also the leader of the innovation team of the national science and Technology Progress Award for “network communication and switching technology”. His research interests include communication and information systems, data science and artificial intelligence. (Email: chc@ndsc.com.cn)

Lan WU was born in 1994. She received the B.E. degree in information engineering from Nanjing University of Aeronautics and Astronautics, Nanjing, China in 2016 and the M.S. degree in machine learning, data science and artificial intelligence from Aalto University, Helsinki, Finland, in 2018. She is currently a Research Assistant of National Digital Switching System Engineering & Technological R&D Center (NDSC). Her research interests include machine learning, big data analysis, network behavior analysis and cyberspace security. (Email: lanwundsc@163.com)

Kai WANG was born in 1980. He received the B.E. degree in information processing from Information Engineering University of PLA, Zhengzhou, China, in 2002 and the M.S. degrees in National Digital Switching System Engineering & Technological R&D Center (NDSC), Zhengzhou, in 2005. He is currently an Associate Research Fellow of NDSC, and he is also the Director of Cross-Disciplinary Technology Department in NDSC. His research interests include link prediction and communication network security. (Email: wangkai0508@126.com)

Xing LI was born in 1987. He received the B.E. degree in information engineering from Information Engineering University of PLA, Zhengzhou, China, in 2009 and the M.S. degrees in Information Engineering University of PLA, Zhengzhou, in 2012. He is currently an Assistant Research Fellow of National Digital Switching System Engineering & Technological R&D Center, and he is also the Deputy Director of Cross-Disciplinary Technology Department in NDSC. His research interests include recommendation system and link prediction. (Email: lixing_ndsc@163.com)
Corresponding author: Email: liushuxin11@126.com
Received Date: 2022-06-10
Accepted Date: 2022-11-15

Available Online: 2023-01-13

Publish Date: 2024-01-05

Abstract

Abstract

Link prediction utilizes accessible network information to complement or predict the network links. Similarity is an important prerequisite for link prediction which means links more likely occurs between two similar nodes. Existing methods utilize the similarity of nodes but neglect of network structure. However the link direction leads to a far more complex structure and contains more information useful than the undirected networks. Most classic methods are difficult to depict the distribution of the network structure with incidental direction so the similarity characteristics of the network structure itself are lost. In this respect, a new method of local structure entropy is proposed to depict the directed structural distribution characteristics, which can be used to evaluate the degree of local structural similarity of nodes and then applied to link prediction methods. Experimental results on 8 real directed networks show that this method is effective for both area under the receiver operating characteristic curve (AUC) and ranking-score measures, and improved predictive capacity of the baseline methodology.
- Local structural entropy,
- Structural complexity,
- Similar nodes,
- Link prediction

FullText(HTML)

References(40)

References

[1]	C. Li, X. S. Ji, S. X. Liu and H. T. Li, “A new method for predicting future links in temporal networks based on node influence,” International Journal of Modern Physics C, vol. 32, no. 12, article no. 2150160, pp.364 ,2021. doi: 10.1142/S0129183121501606
[2]	I. Ahmad, M. U. Akhtar, S. Noor and A. Shahnaz, “Missing link prediction using common neighbor and centrality based parameterized algorithm,” Scientific Reports, vol. 10, no. 1, article no. 364, 2020. doi: 10.1038/s41598-019-57304-y
[3]	S. Scellato, A. Noulas and C. Mascolo, “Exploiting place features in link prediction on location-based social networks,” in Proceedings of the 17th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, San Diego, CA, USA, pp. 1046–1054, 2011.
[4]	J. Leskovec, D. P. Huttenlocher and J. M. Kleinberg, “Governance in social media: a case study of the Wikipedia promotion process,” in Proceedings of the Fourth International Conference on Weblogs and Social Media, Washington, DC, USA, pp. 98–105, 2010.
[5]	V. Martínez, F. Berzal and J. C. Cubero, “A survey of link prediction in complex networks,” ACM Computing Surveys, vol. 49, no. 4, article no. 69, 2017. doi: 10.1145/3012704
[6]	D. Liben-Nowell and J. Kleinberg, “The link-prediction problem for social networks,” Journal of the American Society for Information Science and Technology, vol. 58, no. 7, pp. 1019–1031, 2007. doi: 10.1002/asi.20591
[7]	L. A. Adamic and E. Adar, “Friends and neighbors on the Web,” Social Networks, vol. 25, no. 3, pp. 211–230, 2003. doi: 10.1016/S0378-8733(03)00009-1
[8]	T. Zhou, L. Y. Lü and Y. C. Zhang, “Predicting missing links via local information,” The European Physical Journal B, vol. 71, no. 4, pp. 623–630, 2009. doi: 10.1140/epjb/e2009-00335-8
[9]	M. Mitzenmacher, “A brief history of generative models for power law and lognormal distributions,” Internet Mathematics, vol. 1, no. 2, pp. 226–251, 2004. doi: 10.1080/15427951.2004.10129088
[10]	L. Y. Lü, C. H. Jin and T. Zhou, “Similarity index based on local paths for link prediction of complex networks,” Physical Review E, vol. 80, no. 4, article no. pp.046122, 2009. doi: 10.1103/PhysRevE.80.046122
[11]	S. X. Liu, X. S. Ji, C. X. Liu and Y. Bai , “Extended resource allocation index for link prediction of complex network,” Physica A:Statistical Mechanics and its Applications, vol. 479, pp. 174–183, 2017. doi: 10.1016/j.physa.2017.02.078
[12]	X. Li, S. X. Liu, H. C. Chen and K. Wang, “A potential information capacity index for link prediction of complex networks based on the cannikin law,” Entropy, vol. 21, no. 9, article no. pp.863, 2019. doi: 10.3390/e21090863
[13]	Y. Shang, “Mean commute time for random walks on hierarchical scale-free networks,” Internet Mathematics, vol. 8, no. 4, pp. 321–337, 2012. doi: 10.1080/15427951.2012.685685
[14]	L. Katz, “A new status index derived from sociometric analysis,” Psychometrika, vol. 18, no. 1, pp. 39–43, 1953. doi: 10.1007/BF02289026
[15]	G. Han and W. Wang, “Mapping user relationships for health information diffusion on microblogging in China: a social network analysis of Sina Weibo,” Asian Journal of Communication, vol. 25, no. 1, pp. 65–83, 2015. doi: 10.1080/01292986.2014.989239
[16]	H. Jo, Y. Park, S. E. Kim and H. lee, “Exploring the intellectual structure of nanoscience and nanotechnology: journal citation network analysis,” Journal of Nanoparticle Research, vol. 18, no. 6, pp.1-21, article no. 167, 2016. doi: 10.1007/s11051-016-3473-3
[17]	Y. Kato, M. Kondoh, N. F. Ishikawa, H. Togashi, Y. Kohmatsu and I. Tayasu, “Using food network unfolding to evaluate food–web complexity in terms of biodiversity: theory and applications,” Ecology Letters, vol. 21, no. 7, pp. 1065–1074, 2018. doi: 10.1111/ele.12973
[18]	K. K. Shang, M. Small and W. S. Yan, “Link direction for link prediction,” Physica A:Statistical Mechanics and its Applications, vol. 469, pp. 767–776, 2017. doi: 10.1016/j.physa.2016.11.129
[19]	W. C. Jiang and Y. H. Wang, “Node similarity measure in directed weighted complex network based on node nearest neighbor local network relative weighted entropy,” IEEE Access, vol. 8, pp. 32432–32441, 2020. doi: 10.1109/ACCESS.2020.2971968
[20]	F. Lorrain and H. C. White, “Structural equivalence of individuals in social networks,” The Journal of Mathematical Sociology, vol. 1, no. 1, pp. 49–80, 1971. doi: 10.1080/0022250X.1971.9989788
[21]	M. Dehmer, “Information processing in complex networks: Graph entropy and information functionals,” Applied Mathematics and Computation, vol. 201, no. 1-2, pp. 82–94, 2008. doi: 10.1016/j.amc.2007.12.010
[22]	M. Dehmer and A. Mowshowitz, “A history of graph entropy measures,” Information Sciences, vol. 181, no. 1, pp. 57–78, 2011. doi: 10.1016/j.ins.2010.08.041
[23]	M. Dehmer, K. Varmuza, S. Borgert and F. Emmert-Streib, “On entropy-based molecular descriptors: statistical analysis of real and synthetic chemical structures,” Journal of Chemical Information and Modeling, vol. 49, no. 7, pp. 1655–1663, 2009. doi: 10.1021/ci900060x
[24]	B. Wang, H. W. Tang, C. H. Guo and C. H. Guo, “Entropy optimization of scale-free networks’ robustness to random failures,” Physica A:Statistical Mechanics and its Applications, vol. 363, no. 2, pp. 591–596, 2006. doi: 10.1016/j.physa.2005.08.025
[25]	Q. Zhang, M. Z. Li, and Y. Deng, “A betweenness structure entropy of complex networks,” arXiv preprint, arXiv: 1407.0097, 2014.
[26]	J. T. Zhang and S. A. Wu, “A new species in the genus Crisicoccus Ferris (Hemiptera: Coccomorpha: Pseudococcidae), with a key to Chinese species,” Zootaxa, vol. 4117, no. 3, pp. 440–450, 2016. doi: 10.11646/zootaxa.4117.3.11
[27]	M. Dehmer, F. Emmert-Streib and A. Mehler, Towards an Information Theory of Complex Networks: Statistical Methods and Applications. Springer, New York, NY, USA, pp. 153–167, 2011.
[28]	L. da F. Costa, F. A. Rodrigues, G. Travieso, et al., “Characterization of complex networks: A survey of measurements,” Advances in Physics, vol. 56, no. 1, pp. 167–242, 2007. doi: 10.1080/00018730601170527
[29]	T. Wen and W. Jiang, “Measuring the complexity of complex network by Tsallis entropy,” Physica A:Statistical Mechanics and its Applications, vol. 526, article no. pp.121054, 2019. doi: 10.1016/j.physa.2019.121054
[30]	X. Zhang, C. L. Zhao, X. J. Wang and D. Yi, “Identifying missing and spurious interactions in directed networks,” International Journal of Distributed Sensor Networks, vol. 11, no. 9, pp. 470–481, 2015. doi: 10.1155/2015/507386
[31]	Q. M. Zhang, L. Y. Lü, W. Q. Wang and T.Zhou, “Potential theory for directed networks,” PLoS One, vol. 8, no. 2, article no. e55437, 2013. doi: 10.1371/journal.pone.0055437
[32]	J. A. Hanley and B. J. McNeil, “The meaning and use of the area under a receiver operating characteristic (ROC) curve,” Radiology, vol. 143, no. 1, pp. 29–36, 1982. doi: 10.1148/radiology.143.1.7063747
[33]	T. Zhou, J. Ren, M. Medo and Y. C. Zhang, “Bipartite network projection and personal recommendation,” Physical Review E, vol. 76, no. 4, article no. pp.046115, 2007. doi: 10.1103/PhysRevE.76.046115
[34]	D. S. Sade, “Sociometrics of Macaca mulatta I. Linkages and cliques in grooming matrices,” Folia Primatologica, vol. 18, no. 3-4, pp. 196–223, 1972. doi: 10.1159/000155480
[35]	R. M. Ewing, P. Chu, F. Elisma, H. Li, P. Taylor, S. Climie and D. Figeys, “Large-scale mapping of human protein–protein interactions by mass spectrometry,” Molecular Systems Biology, vol. 31, no. 1, article no. 89, 2007. doi: 10.1038/msb4100134
[36]	P. Bonacich and P. Lu, Introduction to Mathematical Sociology. Princeton University Press, Princeton, NJ, USA, pp. 134 − 146, 2012
[37]	T. Opsahl and P. Panzarasa, “Clustering in weighted networks,” Social Networks, vol. 31, no. 2, pp. 155–163, 2009. doi: 10.1016/j.socnet.2009.02.002
[38]	V. Batagelj, A. Mrvar, and M. Zaveršnik, “Network analysis of texts”, The Third Language Technologies Conference, Ljubljana, Slovenia, pp. 4–6, 2002.
[39]	J. F. Rual, K. Venkatesan, T. Hao, T. Hirozane-Kishikawa, A. Dricot, N. Li and M. Vidal, “Towards a proteome-scale map of the human protein-protein interaction network,” Nature, vol. 437, no. 7062, pp. 1173–1178, 2005. doi: 10.1038/nature04209
[40]	J. J. Kuhlman, B. Levine, M. L. Smith and J. R. Hordinsky, “Toxicological findings in Federal Aviation Administration general aviation accidents,” Journal Forensic Sciences, vol. 36, no. 4, pp. 1121–1128, 1991. doi: 10.1520/JFS13127J