Significance Quantifying a network's link predictability allows us to (i) evaluate predictive algorithms associated with the network, (ii) estimate the extent to which the organization of the network is explicable, and (iii) monitor sudden mechanistic changes during the network's evolution. The hypothesis of this paper is that a group of links is predictable if removing them has only a small effect on the network's structural features. We introduce a quantitative index for measuring link predictability and an algorithm that outperforms state-of-the-art link prediction methods in both accuracy and universality. This study provides fundamental insights into important scientific problems and will aid in the development of information filtering technologies. Abstract The organization of real networks usuallyembodies both regularities and irregularities, and, in principle, the formercan be modeled. The extent to which the formation of a network can be explainedcoincides with our ability to predict missing links. To understand networkorganization, we should be able to estimate link predictability. We assume thatthe regularity of a network is reflected in the consistency of structuralfeatures before and after a random removal of a small set of links. Based on theperturbation of the adjacency matrix, we propose a universal structuralconsistency index that is free of prior knowledge of network organization.Extensive experiments on disparate real-world networks demonstrate that (i)structural consistency is a good estimation of link predictability and (ii) aderivative algorithm outperforms state-of-the-art link prediction methods inboth accuracy and robustness. This analysis has further applications inevaluating link prediction algorithms and monitoring sudden changes in evolvingnetwork mechanisms. It will provide unique fundamental insights into theabove-mentioned academic research fields, and will foster the development ofadvanced information filtering technologies of interest to informationtechnology practitioners. 全文下载地址（免费） http://www.pnas.org/content/112/8/2325.full?sid=61535af6-9110-483a-9370-a9389abd7977 更多详情参见周涛老师博客~ http://blog.sciencenet.cn/home.php?mod=spaceuid=3075do=blogid=867520
Physica A: Statistical Mechanics and its Applications' s top 5 downloaded articles: Link prediction in complex networks: A survey Evolution of the social network of scientific collaborations Identifying influential nodes in complex networks Discovering the influential users oriented to viral marketing based on online social networks Analyzing user behavior of the micro-blogging website Sina Weibo during hot social events
Physics and Astronomy Physica A: Statistical Mechanics and its Applications January to December 2013 full year RSS Blog This! Print Show condensed 1. Link prediction in complex networks: A survey • Review article Physica A: Statistical Mechanics and its Applications, Volume 390, Issue 6, March 2011, Pages 1150-1170 Lü, Linyuan; Zhou, Tao Cited by Scopus (133) 2. The Peter principle revisited: A computational study Physica A: Statistical Mechanics and its Applications, Volume 389, Issue 3, February 2010, Pages 467-472 Pluchino, Alessandro; Rapisarda, Andrea; Garofalo, Cesare Cited by Scopus (16) 3. Evolution of the social network of scientific collaborations Physica A: Statistical Mechanics and its Applications, Volume 311, Issue 3-4, August 2002, Pages 590-614 Barabási, A.L; Jeong, H; Néda, Z; Ravasz, E; Schubert, A; Vicsek, T Cited by Scopus (814) 4. Social network based microblog user behavior analysis Physica A: Statistical Mechanics and its Applications, Volume 392, Issue 7, April 2013, Pages 1712-1723 Yan, Qiang; Wu, Lianren; Zheng, Lan Cited by Scopus (7) 5. Social structure of Facebook networks Physica A: Statistical Mechanics and its Applications, Volume 391, Issue 16, August 2012, Pages 4165-4180 Traud, Amanda L.; Mucha, Peter J.; Porter, Mason A. Cited by Scopus (21) 6. A mathematical model of Gone with the Wind Physica A: Statistical Mechanics and its Applications, Volume 392, Issue 15, August 2013, Pages 3231-3239 Rinaldi, Sergio; Della Rossa, Fabio; Landi, Pietro Cited by Scopus (2) 7. Identifying influential nodes in complex networks Physica A: Statistical Mechanics and its Applications, Volume 391, Issue 4, February 2012, Pages 1777-1787 Chen, Duanbing; Lü, Linyuan; Shang, Ming-Sheng; Zhang, Yi-Cheng; Zhou, Tao Cited by Scopus (42) 8. Mean-field theory for scale-free random networks Physica A: Statistical Mechanics and its Applications, Volume 272, Issue 1-2, October 1999, Pages 173-187 Barabási, Albert-László; Albert, Réka; Jeong, Hawoong 9. Discovering the influential users oriented to viral marketing based on online social networks Physica A: Statistical Mechanics and its Applications, Volume 392, Issue 16, August 2013, Pages 3459-3469 Zhu, Zhiguo 10. The Power Grid as a complex network: A survey Physica A: Statistical Mechanics and its Applications, Volume 392, Issue 11, Pages 2688-2700 Pagani, Giuliano Andrea; Aiello, Marco Cited by Scopus (19) 11. Theory of rumour spreading in complex social networks Physica A: Statistical Mechanics and its Applications, Volume 374, Issue 1, January 2007, Pages 457-470 Nekovee, M.; Moreno, Y.; Bianconi, G.; Marsili, M. Cited by Scopus (105) 12. Identification of overlapping community structure in complex networks using fuzzy c-means clustering Physica A: Statistical Mechanics and its Applications, Volume 374, Issue 1, January 2007, Pages 483-490 Zhang, Shihua; Wang, Rui-Sheng; Zhang, Xiang-Sun Cited by Scopus (176) 13. Multifractal detrended fluctuation analysis of nonstationary time series Physica A: Statistical Mechanics and its Applications, Volume 316, Issue 1-4, December 2002, Pages 87-114 Kantelhardt, Jan W.; Zschiegner, Stephan A.; Koscielny-Bunde, Eva; Havlin, Shlomo; Bunde, Armin; Stanley, H.Eugene Cited by Scopus (790) 14. A study of the spreading scheme for viral marketing based on a complex network model Physica A: Statistical Mechanics and its Applications, Volume 389, Issue 4, February 2010, Pages 859-870 Yang, Jianmei; Yao, Canzhong; Ma, Weicheng; Chen, Guanrong Cited by Scopus (9) 15. Detect overlapping and hierarchical community structure in networks Physica A: Statistical Mechanics and its Applications, Volume 388, Issue 8, April 2009, Pages 1706-1712 Shen, Huawei; Cheng, Xueqi; Cai, Kai; Hu, Mao-Bin Cited by Scopus (131) 16. Simulation of pedestrian dynamics using a two-dimensional cellular automaton Physica A: Statistical Mechanics and its Applications, Volume 295, Issue 3-4, June 2001, Pages 507-525 Burstedde, C; Klauck, K; Schadschneider, A; Zittartz, J Cited by Scopus (528) 17. Correlation of financial markets in times of crisis Physica A: Statistical Mechanics and its Applications, Volume 391, Issue 1-2, January 2012, Pages 187-208 Sandoval, Leonidas; Franca, Italo De Paula Cited by Scopus (27) 18. Scale-free characteristics of random networks: the topology of the world-wide web Physica A: Statistical Mechanics and its Applications, Volume 281, Issue 1-4, June 2000, Pages 69-77 Barabási, Albert-László; Albert, Réka; Jeong, Hawoong 19. The network analysis of urban streets: A dual approach Physica A: Statistical Mechanics and its Applications, Volume 369, Issue 2, September 2006, Pages 853-866 Porta, Sergio; Crucitti, Paolo; Latora, Vito Cited by Scopus (128) 20. Continuous growth models in terms of generalized logarithm and exponential functions • Review article Physica A: Statistical Mechanics and its Applications, Volume 387, Issue 23, October 2008, Pages 5679-5687 Martinez, Alexandre Souto; González, Rodrigo Silva; Terçariol, César Augusto Sangaletti Cited by Scopus (14) 21. Models of vehicular traffic: An engineering perspective Physica A: Statistical Mechanics and its Applications, Volume 372, Issue 1, December 2006, Pages 151-161 Chakroborty, Partha Cited by Scopus (13) 22. Identifying influential nodes in weighted networks based on evidence theory Physica A: Statistical Mechanics and its Applications, Volume 392, Issue 10, Pages 2564-2575 Wei, Daijun; Deng, Xinyang; Zhang, Xiaoge; Deng, Yong; Mahadevan, Sankaran Cited by Scopus (27) 23. Vulnerability analysis of interdependent infrastructure systems: A methodological framework Physica A: Statistical Mechanics and its Applications, Volume 391, Issue 11, June 2012, Pages 3323-3335 Wang, Shuliang; Hong, Liu; Chen, Xueguang Cited by Scopus (13) 24. Criticism of generally accepted fundamentals and methodologies of traffic and transportation theory: A brief review • Review article Physica A: Statistical Mechanics and its Applications, Volume 392, Issue 21, November 2013, Pages 5261-5282 Kerner, Boris S. Cited by Scopus (9) 25. Sand dunes mobility and stability in relation to climate Physica A: Statistical Mechanics and its Applications, Volume 357, Issue 1, November 2005, Pages 50-56 Tsoar, H. Cited by Scopus (93)
Abstract Uncovering factors underlying the network formation is a long-standing challenge for data mining and network analysis. Inparticular, the microscopic organizing principles of directed networks are less understood than those of undirectednetworks. This article proposes a hypothesis named potential theory, which assumes that every directed link corresponds toa decrease of a unit potential and subgraphs with definable potential values for all nodes are preferred. Combining thepotential theory with the clustering and homophily mechanisms, it is deduced that the Bi-fan structure consisting of 4nodes and 4 directed links is the most favored local structure in directed networks. Our hypothesis receives strongly positivesupports from extensive experiments on 15 directed networks drawn from disparate fields, as indicated by the mostaccurate and robust performance of Bi-fan predictor within the link prediction framework. In summary, our maincontribution is twofold: (i) We propose a new mechanism for the local organization of directed networks; (ii) We design thecorresponding link prediction algorithm, which can not only testify our hypothesis, but also find out direct applications in missing link prediction and friendship recommendation. Citation: Zhang Q-M, Lu L, Wang W-Q, Zhu Y-X, Zhou T. (2013) Potential Theory for Directed Networks. PLoS ONE 8(2): e55437. doi:10.1371/journal.pone.0055437 Download： journal.pone.0055437.pdf 相关博文： http://blog.sciencenet.cn/home.php?mod=spaceuid=3075do=blogid=664452
Nonlinear and Statistical Physics Top 20 most downloaded articles in this subject, 2011 The articles are listed below hierarchically and based on download data for 2011 from Elsevier's online platform SciVerse ScienceDirect. 1 Applications of ultrasound in food technology: Processing, preservation and extraction Ultrasonics Sonochemistry Chemat, F.; Zill-e-Huma; Khan, M.K. 2 Low-carbon building assessment and multi-scale input-output analysis Communications in Nonlinear Science and Numerical Simulation Chen, G.Q.; Chen, H.; Chen, Z.M.; Zhang, B.; Shao, L.; Guo, S.; Zhou, S.Y.; Jiang, M.M. 3 Using sonochemistry for the fabrication of nanomaterials Ultrasonics Sonochemistry Gedanken, A. 4 Nonlinear dynamics for broadband energy harvesting: Investigation of a bistable piezoelectric inertial generator Physica D: Nonlinear Phenomena Stanton, S.C.; McGehee, C.C.; Mann, B.P. 5 Zinc oxide nano-particles - Sonochemical synthesis, characterization and application for photo-remediation of heavy metal Ultrasonics Sonochemistry Banerjee, P.; Chakrabarti, S.; Maitra, S.; Dutta, B.K. 6 Therapeutic ultrasound an overview Ultrasonics Sonochemistry Mason, T.J. 7 A study of the spreading scheme for viral marketing based on a complex network model Physica A: Statistical Mechanics and its Applications Yang, J.; Yao, C.; Ma, W.; Chen, G. 8 Link prediction in complex networks: A survey Physica A: Statistical Mechanics and its Applications Lu, L.; Zhou, T. 9 The characterization of acoustic cavitation bubbles - An overview Ultrasonics Sonochemistry Ashokkumar, M. 10 Graphene oxide based Pt-TiO"2 photocatalyst: Ultrasound assisted synthesis, characterization and catalytic efficiency Ultrasonics Sonochemistry Neppolian, B.; Bruno, A.; Bianchi, C.L.; Ashokkumar, M. 11 The behavior of a many-particle electrode in a lithium-ion battery Physica D: Nonlinear Phenomena Dreyer, W.; Guhlke, C.; Huth, R. 12 Evacuation dynamics with fire spreading based on cellular automaton Physica A: Statistical Mechanics and its Applications Zheng, Y.; Jia, B.; Li, X.G.; Zhu, N. 13 Mean-field theory for scale-free random networks Physica A: Statistical Mechanics and its Applications Barabasi, A.-L.; Albert, R.; Jeong, H. 14 Improved extraction of vegetable oils under high-intensity ultrasound and/or microwaves Ultrasonics Sonochemistry Cravotto, G.; Boffa, L.; Mantegna, S.; Perego, P.; Avogadro, M.; Cintas, P. 15 Sonochemical synthesis of TiO"2 nanoparticles on graphene for use as photocatalyst Ultrasonics Sonochemistry Guo, J.; Zhu, S.; Chen, Z.; Li, Y.; Yu, Z.; Liu, Q.; Li, J.; Feng, C.; Zhang, D. 16 The Peter principle revisited: A computational study Physica A: Statistical Mechanics and its Applications Pluchino, A.; Rapisarda, A.; Garofalo, C. 17 Evolution of the social network of scientific collaborations Physica A: Statistical Mechanics and its Applications Barabasi, A.L.; Jeong, H.; Neda, Z.; Ravasz, E.; Schubert, A.; Vicsek, T. 18 Ultrasonic pretreatment of sludge: A review Ultrasonics Sonochemistry Pilli, S.; Bhunia, P.; Yan, S.; LeBlanc, R.J.; Tyagi, R.D.; Surampalli, R.Y. 19 Advanced oxidation processes (AOPs) involving ultrasound for waste water treatment: A review with emphasis on cost estimation Ultrasonics Sonochemistry Mahamuni, N.N.; Adewuyi, Y.G. 20 Fast and easy synthesis of core-shell nanocrystal (CdS/TiO"2) at low temperature by micro-emulsion under ultrasound Ultrasonics Sonochemistry Ghows, N.; Entezari, M.H.
《链路预测综述》成为Physica A 2011年发表文章中的最热门文章~ Physica A: Statistical Mechanics and its Applications January to December 2011 full year 1. !-- /a-- The Peter principle revisited: A computational study Physica A: Statistical Mechanics and its Applications, Volume 389, Issue 3, February 2010, Pages 467-472 Pluchino, A.; Rapisarda, A.; Garofalo, C. !-- Bookmark article/a -- Cited by SciVerse Scopus (5) 2. !-- /a-- Evolution of the social network of scientific collaborations Physica A: Statistical Mechanics and its Applications, Volume 311, Issue 3-4, August 2002, Pages 590-614 Barabasi, A.L.; Jeong, H.; Neda, Z.; Ravasz, E.; Schubert, A.; Vicsek, T. !-- Bookmark article/a -- Cited by SciVerse Scopus (528) 3. !-- /a-- A study of the spreading scheme for viral marketing based on a complex network model Physica A: Statistical Mechanics and its Applications, Volume 389, Issue 4, February 2010, Pages 859-870 Yang, J.; Yao, C.; Ma, W.; Chen, G. !-- Bookmark article/a -- Cited by SciVerse Scopus (2) 4. !-- /a-- Link prediction in complex networks: A survey • Review article Physica A: Statistical Mechanics and its Applications, Volume 390, Issue 6, March 2011, Pages 1150-1170 Lu, L.; Zhou, T. !-- Bookmark article/a -- Cited by SciVerse Scopus (11) 5. !-- /a-- Evacuation dynamics with fire spreading based on cellular automaton Physica A: Statistical Mechanics and its Applications, Volume 390, Issue 18-19, September 2011, Pages 3147-3156 Zheng, Y.; Jia, B.; Li, X.G.; Zhu, N. !-- Bookmark article/a -- Cited by SciVerse Scopus (1) 6. !-- /a-- Mean-field theory for scale-free random networks Physica A: Statistical Mechanics and its Applications, Volume 272, Issue 1-2, October 1999, Pages 173-187 Barabasi, A.-L.; Albert, R.; Jeong, H. !-- Bookmark article/a -- 7. !-- /a-- Efficient promotion strategies in hierarchical organizations Physica A: Statistical Mechanics and its Applications, Volume 390, Issue 20, October 2011, Pages 3496-3511 Pluchino, A.; Rapisarda, A.; Garofalo, C. !-- Bookmark article/a -- Cited by SciVerse Scopus (2) 8. !-- /a-- Empirical analysis of online social networks in the age of Web 2.0 Physica A: Statistical Mechanics and its Applications, Volume 387, Issue 2-3, January 2008, Pages 675-684 Fu, F.; Liu, L.; Wang, L. !-- Bookmark article/a -- Cited by SciVerse Scopus (29) 9. !-- /a-- Evolutionary game theory: Theoretical concepts and applications to microbial communities Physica A: Statistical Mechanics and its Applications, Volume 389, Issue 20, October 2010, Pages 4265-4298 Frey, E. !-- Bookmark article/a -- Cited by SciVerse Scopus (9) 10. !-- /a-- Multifractal detrending moving average analysis on the US Dollar exchange rates Physica A: Statistical Mechanics and its Applications, Volume 390, Issue 20, October 2011, Pages 3512-3523 Wang, Y.; Wu, C.; Pan, Z. !-- Bookmark article/a -- Cited by SciVerse Scopus (2) 11. !-- /a-- Estimating risk of foreign exchange portfolio: Using VaR and CVaR based on GARCH-EVT-Copula model Physica A: Statistical Mechanics and its Applications, Volume 389, Issue 21, November 2010, Pages 4918-4928 Wang, Z.R.; Chen, X.H.; Jin, Y.B.; Zhou, Y.J. !-- Bookmark article/a -- Cited by SciVerse Scopus (2) 12. !-- /a-- Identification of overlapping community structure in complex networks using fuzzy c-means clustering Physica A: Statistical Mechanics and its Applications, Volume 374, Issue 1, January 2007, Pages 483-490 Zhang, S.; Wang, R.S.; Zhang, X.-S. !-- Bookmark article/a -- Cited by SciVerse Scopus (90) 13. !-- /a-- Thermomechanical properties of the WCA-Lennard-Jones model system in its fluid and solid states Physica A: Statistical Mechanics and its Applications, Volume 250, Issue 1-4, February 1998, Pages 58-82 Hess, S.; Kroger, M.; Voigt, H. !-- Bookmark article/a -- Cited by SciVerse Scopus (25) 14. !-- /a-- Statistical models for operational risk management Physica A: Statistical Mechanics and its Applications, Volume 338, Issue 1-2, July 2004, Pages 166-172 Cornalba, C.; Giudici, P. !-- Bookmark article/a -- Cited by SciVerse Scopus (22) 15. !-- /a-- Statistical analysis of daily gold price data Physica A: Statistical Mechanics and its Applications, Volume 338, Issue 3-4, July 2004, Pages 559-566 Mills, T.C. !-- Bookmark article/a -- Cited by SciVerse Scopus (5) 16. !-- /a-- Online social networks-Paradise of computer viruses Physica A: Statistical Mechanics and its Applications, Volume 390, Issue 2, January 2011, Pages 189-197 Fan, W.; Yeung, K.H. !-- Bookmark article/a -- 17. !-- /a-- Multifractal detrended fluctuation analysis of nonstationary time series Physica A: Statistical Mechanics and its Applications, Volume 316, Issue 1-4, December 2002, Pages 87-114 Kantelhardt, J.W.; Zschiegner, S.A.; Koscielny-Bunde, E.; Havlin, S.; Bunde, A.; Stanley, H.E. !-- Bookmark article/a -- Cited by SciVerse Scopus (434) 18. !-- /a-- Theory of rumour spreading in complex social networks Physica A: Statistical Mechanics and its Applications, Volume 374, Issue 1, January 2007, Pages 457-470 Nekovee, M.; Moreno, Y.; Bianconi, G.; Marsili, M. !-- Bookmark article/a -- Cited by SciVerse Scopus (30) 19. !-- /a-- Hierarchical structure of Turkey's foreign trade Physica A: Statistical Mechanics and its Applications, Volume 390, Issue 20, October 2011, Pages 3454-3476 Kantar, E.; Deviren, B.; Keskin, M. !-- Bookmark article/a -- Cited by SciVerse Scopus (2) 20. !-- /a-- Detect overlapping and hierarchical community structure in networks Physica A: Statistical Mechanics and its Applications, Volume 388, Issue 8, April 2009, Pages 1706-1712 Shen, H.; Cheng, X.; Cai, K.; Hu, M.B. !-- Bookmark article/a -- Cited by SciVerse Scopus (46) 21. !-- /a-- Correlation of financial markets in times of crisis Physica A: Statistical Mechanics and its Applications, Volume 391, Issue 1-2, January 2012, Pages 187-208 Sandoval, L.; Franca, I.D.P. !-- Bookmark article/a -- Cited by SciVerse Scopus (2) 22. !-- /a-- The 2006-2008 oil bubble: Evidence of speculation, and prediction Physica A: Statistical Mechanics and its Applications, Volume 388, Issue 8, April 2009, Pages 1571-1576 Sornette, D.; Woodard, R.; Zhou, W.X. !-- Bookmark article/a -- Cited by SciVerse Scopus (17) 23. !-- /a-- Value-at-risk estimation with wavelet-based extreme value theory: Evidence from emerging markets Physica A: Statistical Mechanics and its Applications, Volume 390, Issue 12, June 2011, Pages 2356-2367 Cifter, A. !-- Bookmark article/a -- Cited by SciVerse Scopus (1) 24. !-- /a-- Simulation of pedestrian dynamics using a two-dimensional cellular automaton Physica A: Statistical Mechanics and its Applications, Volume 295, Issue 3-4, June 2001, Pages 507-525 Burstedde, C.; Klauck, K.; Schadschneider, A.; Zittartz, J. !-- Bookmark article/a -- Cited by SciVerse Scopus (312) 25. !-- /a-- Scale-free characteristics of random networks: the topology of the world-wide web Physica A: Statistical Mechanics and its Applications, Volume 281, Issue 1-4, June 2000, Pages 69-77 Barabasi, A.-L.; Albert, R.; Jeong, H. !-- Bookmark article/a --
无标度网络中的链路预测问题研究 作者： 王 林，商 超 (西安理工大学自动化与信息工程学院，西安 710048) 摘 要： 研究无标度网络中的链路预测问题。针对人造网络和实际社会网络，分别介绍静态和动态2 种链路预测的实现过程，探究利用相似性进行链路预测的可行性，并验证多种相似度计算方法的准确性。对预测结果进行有效性分析，同时根据不同网络特性给出相应的预测算法。 关键词： 复杂网络；信息检索；无标度；链路预测；拓扑结构；相似性 DOI: 10.3969/j.issn.1000-3428.2012.03.023 全文下载： Research on Link Prediction Problem in Scale-free Network.pdf
标签: 链路预测
