A New Link Prediction Method for Complex Networks Based on Resources Carrying Capacity Between Nodes

Kai WANG; Shuxin LIU; Hongchang CHEN; Xing LI

doi:10.11999/JEIT180553

Volume 41 Issue 5

Apr. 2019

Turn off MathJax

Article Contents

Article Navigation > Journal of Electronics & Information Technology > 2019 > 41(5): 1225-1234

Kai WANG, Shuxin LIU, Hongchang CHEN, Xing LI. A New Link Prediction Method for Complex Networks Based on Resources Carrying Capacity Between Nodes[J]. Journal of Electronics & Information Technology, 2019, 41(5): 1225-1234. doi: 10.11999/JEIT180553

Citation:

Kai WANG, Shuxin LIU, Hongchang CHEN, Xing LI. A New Link Prediction Method for Complex Networks Based on Resources Carrying Capacity Between Nodes[J]. Journal of Electronics & Information Technology, 2019, 41(5): 1225-1234. doi: 10.11999/JEIT180553

Citation:

PDF( 4487 KB)

A New Link Prediction Method for Complex Networks Based on Resources Carrying Capacity Between Nodes

doi: 10.11999/JEIT180553

National Digital Switching System Engineering and Technological R&D Center, Zhengzhou 450002, China

Funds: The National Natural Science Foundation of China (61521003, 61803384)

Received Date: 2018-06-05
Rev Recd Date: 2019-01-16

Available Online: 2019-01-30

Publish Date: 2019-05-01

Abstract

Abstract

Link prediction aims to discover the unknown or missing links of complex networks, which plays an important role in practical application. The similarity-based link prediction methods attract a lot of attention due to their briefness and effectiveness. However, most of similarity indices ignore the influence of resource carrying capacity between nodes when calculating the likelihood that a link exists between two endpoints. Because of the problem, a new link prediction method based on resources carrying capacity between nodes is proposed. Firstly, the resource carrying capacity is proposed to quantify the capability of resource carrying between nodes. Then, based on the resource carrying capacity, a new link prediction method is proposed by analyzing the impact of node connectivity. The experimental results of nine real networks show that compared with other link prediction methods, the proposed method can achieve higher prediction accuracy under three standard metrics.
- Complex network,
- Link prediction,
- Resources carrying capacity,
- Similarity

FullText(HTML)

References(37)

References

SHANMUKHAPPA T, HO I W H, and TSE C K. Spatial analysis of bus transport networks using network theory[J]. Physica A: Statistical Mechanics and Its Applications, 2018, 502: 295–314. doi: 10.1016/j.physa.2018.02.111

CUI Ying, CAI Meng, DAI Yang, et al. A hybrid network-based method for the detection of disease-related genes[J]. Physica A: Statistical Mechanics and Its Applications, 2018, 492: 389–394. doi: 10.1016/j.physa.2017.10.026

VINCENOT C E. How new concepts become universal scientific approaches: insights from citation network analysis of agent-based complex systems science[J]. Proceedings of the Royal Society B: Biological Sciences, 2018, 285(1874): 20172360. doi: 10.1098/rspb.2017.2360

CHEN Zhenhao, WU Jiajing, XIA Yongxiang, et al. Robustness of interdependent power grids and communication networks: A complex network perspective[J]. IEEE Transactions on Circuits and Systems II: Express Briefs, 2018, 65(1): 115–119. doi: 10.1109/TCSII.2017.2705758

KIM J and HASTAK M. Social network analysis: characteristics of online social networks after a disaster[J]. International Journal of Information Management, 2018, 38(1): 86–96. doi: 10.1016/j.ijinfomgt.2017.08.003

VON MERING C, JENSEN L J, SNEL B, et al. STRING: known and predicted protein-protein associations, integrated and transferred across organisms[J]. Nucleic Acids Research, 2005, 33(1): D433–D437. doi: 10.1093/nar/gki005

SCELLATO S, NOULAS A, and MASCOLO C. Exploiting place features in link prediction on location-based social networks[C]. Proceedings of the 17th ACM Sigkdd International Conference on Knowledge Discovery and Data Mining, San Diego, California, USA, 2011: 1046–1054. doi: 10.1145/2020408.2020575.

HOLLAND P W, LASKEY K B, and LEINHARDT S. Stochastic blockmodels: first steps[J]. Social Networks, 1983, 5(2): 109–137. doi: 10.1016/0378-8733(83)90021-7

SANZ-CRUZADO J, PEPA S M, and CASTELLS P. Structural novelty and diversity in link prediction[C]. Companion of the the Web Conference, 2018, Lyon, France, 2018: 1347–1351.

LORRAIN F and WHITE H C. Structural equivalence of individuals in social networks[J]. The Journal of Mathematical Sociology, 1971, 1(1): 49–80. doi: 10.1080/0022250X.1971.9989788

ZHOU Tao, LÜ Linyuan, and ZHANG Yicheng. Predicting missing links via local information[J]. The European Physical Journal B, 2009, 71(4): 623–630. doi: 10.1140/epjb/e2009-00335-8

ADAMIC L A and ADAR E. Friends and neighbors on the web[J]. Social Networks, 2003, 25(3): 211–230. doi: 10.1016/S0378-8733(03)00009-1

CANNISTRACI C V, ALANIS-LOBATO G, and RAVASI T. From link-prediction in brain connectomes and protein interactomes to the local-community-paradigm in complex networks[J]. Scientific Reports, 2013(3): 1613. doi: 10.1038/srep01613

LIU Shuxin, JI Xinsheng, LIU Caixia, et al. Extended resource allocation index for link prediction of complex network[J]. Physica A: Statistical Mechanics and Its Applications, 2017, 479: 174–183. doi: 10.1016/j.physa.2017.02.078

KATZ L. A new status index derived from sociometric analysis[J]. Psychometrika, 1953, 18(1): 39–43. doi: 10.1007/BF02289026

KLEIN D J and RANDIĆ M. Resistance distance[J]. Journal of Mathematical Chemistry, 1993, 12(1): 81–95. doi: 10.1007/BF01164627

FOUSS F, PIROTTE A, RENDERS J M, et al. Random-walk computation of similarities between nodes of a graph with application to collaborative recommendation[J]. IEEE Transactions on Knowledge and Data Engineering, 2007, 19(3): 355–369. doi: 10.1109/tkde.2007.46

LÜ Linyuan, JIN Cihang, and ZHOU Tao. Similarity index based on local paths for link prediction of complex networks[J]. Physical Review E, 2009, 80(4): 046122. doi: 10.1103/PhysRevE.80.046122

YANG Yujie, ZHANG Jianhua, ZHU Xuzhen, et al. Link prediction via significant influence[J]. Physica A: Statistical Mechanics and Its Applications, 2018, 492: 1523–1530. doi: 10.1016/j.physa.2017.11.078

刘树新, 季新生, 刘彩霞, 等. 一种信息传播促进网络增长的网络演化模型[J]. 物理学报, 2014, 63(15): 158902. doi: 10.7498/aps.63.158902

LIU Shuxin, JI Xinsheng, LIU Caixia, et al. A complex network evolution model for network growth promoted by information transmission[J]. Acta Physica Sinica, 2014, 63(15): 158902. doi: 10.7498/aps.63.158902

WANG Xingyuan, ZHOU Wenjie, LI Rui, et al. Improving robustness of interdependent networks by a new coupling strategy[J]. Physica A: Statistical Mechanics and Its Applications, 2018, 492: 1075–1080. doi: 10.1016/j.physa.2017.11.037

WANG Xingyuan, CAO Jianye, LI Rui, et al. A preferential attachment strategy for connectivity link addition strategy in improving the robustness of interdependent networks[J]. Physica A: Statistical Mechanics and Its Applications, 2017, 483: 412–422. doi: 10.1016/j.physa.2017.04.128

WANG Xingyuan, CAO Jianye, and QIN Xiaomeng. Study of robustness in functionally identical coupled networks against cascading failures[J]. PLoS One, 2016, 11(8): e0160545. doi: 10.1371/journal.pone.0160545

DEWHURST D R, DANFORTH C M, and DODDS P S. Continuum rich-get-richer processes: mean field analysis with an application to firm size[J]. Physical Review E, 2018, 97(6): 062317. doi: 10.1103/PhysRevE.97.062317

ZENG Guoping and ZENG E. On the three-way equivalence of AUC in credit scoring with tied scores[J]. Communications in Statistics-Theory and Methods, 2017, 46(17): 1–16. doi: 10.1080/03610926.2018.1435814

WU Zhihao, LIN Youfang, ZHAO Yiji, et al. Improving local clustering based top-L link prediction methods via asymmetric link clustering information[J]. Physica A: Statistical Mechanics and Its Applications, 2018, 492: 1859–1874. doi: 10.1016/j.physa.2017.11.103

ZENG Xiangxiang, LIU Li, LÜ Linyuan, et al. Prediction of potential disease-associated microRNAs using structural perturbation method[J]. Bioinformatics, 2018, 34(14): 2425–2432. doi: 10.1093/bioinformatics/bty112

GOPAL S. The evolving social geography of blogs[M]. MILLER H J. Societies and Cities in the Age of Instant Access. Dordrecht, Springer, 2007: 275–293. doi: 10.1007/1-4020-5427-0_18.

MICHALSKI R, PALUS S, and KAZIENKO P. Matching organizational structure and social network extracted from email communication[C]. Proceedings of the 14th International Conference on Business Information Systems, Poznań, Poland, 2011.

ULANOWICZ R E and DEANGELIS D L. Network analysis of trophic dynamics in south Florida ecosystems[J]. US Geological Survey Program on the South Florida Ecosystem, 2005, 114: 45–47. (未找到本条文献信息, 请核对

WATTS D J and STROGATZ S H. Collective dynamics of ‘small-world’ networks[J]. Nature, 1998, 393(6684): 440–442. doi: 10.1038/30918

ADAMIC L A and GLANCE N. The political blogosphere and the 2004 U.S. election: divided they blog[C]. Proceedings of the 3rd International Workshop on Link Discovery, Chicago, USA, 2005: 36–43. doi: 10.1145/1134271.1134277.

LÜ Linyuan, PAN Liming, ZHOU Tao, et al. Toward link predictability of complex networks[J]. Proceedings of the National Academy of Sciences of the United States of America, 2015, 112(8): 2325–2330. doi: 10.1073/pnas.1424644112

EWING R M, CHU P, ELISMA F, et al. Large-scale mapping of human protein-protein interactions by mass spectrometry[J]. Molecular Systems Biology, 2007, 3: 89. doi: 10.1038/msb4100134

OPSAHL T and PANZARASA P. Clustering in weighted networks[J]. Social Networks, 2009, 31(2): 155–163. doi: 10.1016/j.socnet.2009.02.002

刘树新, 季新生, 刘彩霞, 等. 局部拓扑信息耦合促进网络演化[J]. 电子与信息学报, 2016, 38(9): 2180–2187. doi: 10.11999/JEIT151338

LIU Shuxin, JI Xinsheng, LIU Caixia, et al. Information coupling of local topology promoting the network evolution[J]. Journal of Electronics &Information Technology, 2016, 38(9): 2180–2187. doi: 10.11999/JEIT151338

Relative Articles

Supplements(0)

Cited By

Proportional views