Link prediction in complex networks: A survey
Physica A Statistical Mechanics and its ApplicationsPublished 3 December 2010Open access
Linyuan Lü, Tao Zhou
Citations2,763
Generate an AI Snapshot to get a quick, structured summary of this paper.
Study Snapshot
ObjectiveStudy objective
MethodsResearch methodology
PopulationPopulation studied
Sample sizeSample sizes
OutcomesStudy outcomes here
ResultsStudy results comes here
LimitationsResearch study limitations comes here
A concise AI-generated summary of the paper will appear here once you click Generate AI Snapshot.
TL;DR
Recent progress about link prediction algorithms is summarized, emphasizing on the contributions from physical perspectives and approaches, such as the random-walk-based methods and the maximum likelihood methods.
Abstract
Link prediction in complex networks has attracted increasing attention from\nboth physical and computer science communities. The algorithms can be used to\nextract missing information, identify spurious interactions, evaluate network\nevolving mechanisms, and so on. This article summaries recent progress about\nlink prediction algorithms, emphasizing on the contributions from physical\nperspectives and approaches, such as the random-walk-based methods and the\nmaximum likelihood methods. We also introduce three typical applications:\nreconstruction of networks, evaluation of network evolving mechanism and\nclassification of partially labelled networks. Finally, we introduce some\napplications and outline future challenges of link prediction algorithms.\n
Keywords
Computer SciencePhysics and Astronomy
NatureCollective dynamics of ‘small-world’ networks
43,160 Citations1998Duncan J. Watts, Steven H. Strogatz
Simple models of networks that can be tuned through this middle ground: regular networks ‘rewired’ to introduce increasing amounts of disorder are explored, finding that these systems can be highly clustered, like regular lattices, yet have small characteristic path lengths, like random graphs.
The Journal of Chemical PhysicsEquation of State Calculations by Fast Computing Machines
37,074 Citations1953N. Metropolis, Arianna W. Rosenbluth +3 more
ScienceEmergence of Scaling in Random Networks
36,366 Citations1999Albert-Ĺaszló Barabási, Réka Albert
A model based on these two ingredients reproduces the observed stationary scale-free distributions, which indicates that the development of large networks is governed by robust self-organizing phenomena that go beyond the particulars of the individual systems.
EconometricaInvestigating Causal Relations by Econometric Models and Cross-spectral Methods
22,877 Citations1969Clive W. J. Granger
RadiologyThe meaning and use of the area under a receiver operating characteristic (ROC) curve.
21,812 Citations1982J A Hanley, Barbara J. McNeil
A representation and interpretation of the area under a receiver operating characteristic (ROC) curve obtained by the "rating" method, or by mathematical predictions based on patient characteristics, is presented and it is shown that in such a setting the area represents the probability that a randomly chosen diseased subject is (correctly) rated or ranked with greater suspicion than a random chosen non-diseased subject.
Reviews of Modern PhysicsStatistical mechanics of complex networks
20,607 Citations2002Réka Albert, Albert-Ĺaszló Barabási
A simple model based on these two principles was able to reproduce the power-law degree distribution of real networks, indicating a heterogeneous topology in which the majority of the nodes have a small degree, but there is a significant fraction of highly connected nodes that play an important role in the connectivity of the network.
SIAM ReviewThe Structure and Function of Complex Networks
18,742 Citations2003Michael Newman
Developments in this field are reviewed, including such concepts as the small-world effect, degree distributions, clustering, network correlations, random graph models, models of network growth and preferential attachment, and dynamical processes taking place on networks.
Computer Networks and ISDN SystemsThe anatomy of a large-scale hypertextual Web search engine
15,828 Citations1998Sergey Brin, Lawrence M. Page
This paper provides an in-depth description of Google, a prototype of a large-scale search engine which makes heavy use of the structure present in hypertext and looks at the problem of how to effectively deal with uncontrolled hypertext collections where anyone can publish anything they want.
Proceedings of the National Academy of SciencesCommunity structure in social and biological networks
15,656 Citations2002Michelle Girvan, M. E. J. Newman
This article proposes a method for detecting communities, built around the idea of using centrality indices to find community boundaries, and tests it on computer-generated and real-world graphs whose community structure is already known and finds that the method detects this known structure with high sensitivity and reliability.
The Annals of Mathematical StatisticsOn a Test of Whether one of Two Random Variables is Stochastically Larger than the Other
13,914 Citations1947H. B. Mann, Douglas R. Whitney
Physical Review EFinding and evaluating community structure in networks
13,892 Citations2004Michelle G. Newman, Michelle Girvan
It is demonstrated that the algorithms proposed are highly effective at discovering community structure in both computer-generated and real-world network data, and can be used to shed light on the sometimes dauntingly complex structure of networked systems.
Physics ReportsComplex networks: Structure and dynamics
11,022 Citations2006Stefano Boccaletti, Vito Latora +3 more
The major concepts and results recently achieved in the study of the structure and dynamics of complex networks are reviewed, and the relevant applications of these ideas in many different disciplines are summarized, ranging from nonlinear science to biology, from statistical mechanics to medicine and engineering.
Psychological MethodsMissing data: Our view of the state of the art.
10,918 Citations2002Joseph L. Schafer, J. A. Graham
2 general approaches that come highly recommended: maximum likelihood (ML) and Bayesian multiple imputation (MI) are presented and may eventually extend the ML and MI methods that currently represent the state of the art.
Cambridge University Press eBooksIntroduction to Information Retrieval
10,873 Citations2008Christopher D. Manning, Prabhakar Raghavan +1 more
This textbook teaches classical and web information retrieval, including web search and the related areas of text classification and text clustering from basic concepts, making it perfect for introductory courses in information retrieval for advanced undergraduates and graduate students in computer science.
A study of cross-validation and bootstrap for accuracy estimation and model selection
10,733 Citations1995Ron Kohavi
The results indicate that for real-word datasets similar to the authors', the best method to use for model selection is ten fold stratified cross validation even if computation power allows using more folds.
Philosophical transactions of the Royal Society of London. Series B, Biological sciencesThe structure of the nervous system of the nematode <i>Caenorhabditis elegans</i>
5,836 Citations1986JG White, Eileen Southgate +2 more
The structure and connectivity of the nervous system of the nematode Caenorhabditis elegans has been deduced from reconstructions of electron micrographs of serial sections.
ACM Transactions on Information SystemsEvaluating collaborative filtering recommender systems
5,762 Citations2004Jonathan L. Herlocker, Joseph A. Konstan +2 more
The key decisions in evaluating collaborative filtering recommender systems are reviewed: the user tasks being evaluated, the types of analysis and datasets being used, the ways in which prediction quality is measured, the evaluation of prediction attributes other than quality, and the user-based evaluation of the system as a whole.
Proceedings of the 25th international conference on Machine learning
5,542 Citations2008William W. Cohen, Andrew McCallum +1 more
Statistical Inference
5,368 Citations1993George Casella, Roger L. Berger
Physical Review LettersAssortative Mixing in Networks
4,980 Citations2002M. E. J. Newman
This work proposes a model of an assortatively mixed network and finds that networks percolate more easily if they are assortative and that they are also more robust to vertex removal.
Physical Review EFinding community structure in networks using the eigenvectors of matrices
4,801 Citations2006M. E. J. Newman
A modularity matrix plays a role in community detection similar to that played by the graph Laplacian in graph partitioning calculations, and a spectral measure of bipartite structure in networks and a centrality measure that identifies vertices that occupy central positions within the communities to which they belong are proposed.
Cambridge University Press eBooksInvestigating Causal Relations by Econometric Models and Cross-Spectral Methods
4,797 Citations2010Clive W. J. Granger
Journal of Anthropological ResearchAn Information Flow Model for Conflict and Fission in Small Groups
4,661 Citations1977Wayne Zachary
Mathematical Proceedings of the Cambridge Philosophical SocietyA generalized inverse for matrices
4,495 Citations1955Roger Penrose
ScienceHierarchical Organization of Modularity in Metabolic Networks
4,291 Citations2002E. Ravasz, A. L. Somera +3 more
It is shown that the metabolic networks of 43 distinct organisms are organized into many small, highly connected topologic modules that combine in a hierarchical manner into larger, less cohesive units, with their number and degree of clustering following a power law.
PsychometrikaA New Status Index Derived from Sociometric Analysis
3,863 Citations1953Leo Katz
A new method of computation which takes into account who chooses as well as how many choose is presented, which introduces the concept of attenuation in influence transmitted through intermediaries.
User Modeling and User-Adapted InteractionHybrid Recommender Systems: Survey and Experiments
3,764 Citations2002Robin Burke
This paper surveys the landscape of actual and possible hybrid recommenders, and introduces a novel hybrid, EntreeC, a system that combines knowledge-based recommendation and collaborative filtering to recommend restaurants, and shows that semantic ratings obtained from the knowledge- based part of the system enhance the effectiveness of collaborative filtering.
An Information-Theoretic Definition of Similarity
3,662 Citations1998Dekang Lin
This work presents an informationtheoretic definition of similarity that is applicable as long as there is a probabilistic model and demonstrates how this definition can be used to measure the similarity in a number of different domains.
Physics ReportsSynchronization in complex networks
3,651 Citations2008Àlex Arenas, Albert Dı́az-Guilera +3 more
The advances in the comprehension of synchronization phenomena when oscillating elements are constrained to interact in a complex network topology are reported and the new emergent features coming out from the interplay between the structure and the function of the underlying pattern of connections are overviewed.
Advances in Artificial IntelligenceA Survey of Collaborative Filtering Techniques
3,602 Citations2009Xiaoyuan Su, Taghi M. Khoshgoftaar
From basic techniques to the state-of-the-art, this paper attempts to present a comprehensive survey for CF techniques, which can be served as a roadmap for research and practice in this area.
Nature Reviews GeneticsNetwork motifs: theory and experimental approaches
3,311 Citations2007Uri Alon
Network motifs are reviewed, suggesting that they serve as basic building blocks of transcription networks, including signalling and neuronal networks, in diverse organisms from bacteria to humans.
Machine LearningLearning Bayesian Networks: The Combination of Knowledge and Statistical Data
3,242 Citations1995David Heckerman, Dan Geiger +1 more
A methodology for assessing informative priors needed for learning Bayesian networks from a combination of prior knowledge and statistical data is developed and how to compute the relative posterior probabilities of network structures given data is shown.
Monte Carlo Methods in Statistical Physics
3,178 Citations1999M. E. J. Newman, G. T. Barkema
Advances In PhysicsEvolution of networks
3,140 Citations2002S. N. Dorogovt︠s︡ev, J. F. F. Mendes
The recent rapid progress in the statistical physics of evolving networks is reviewed, and how growing networks self-organize into scale-free structures is discussed, and the role of the mechanism of preferential linking is investigated.
Physical review. E, Statistical physics, plasmas, fluids, and related interdisciplinary topicsMixing patterns in networks
3,076 Citations2003M. E. J. Newman
This work proposes a number of measures of assortative mixing appropriate to the various mixing types, and applies them to a variety of real-world networks, showing that assortsative mixing is a pervasive phenomenon found in many networks.
Journal of the American Society for Information Science and TechnologyThe link‐prediction problem for social networks
3,024 Citations2007David Liben‐Nowell, Jon Kleinberg
Social NetworksFriends and neighbors on the Web
2,885 Citations2003Lada A. Adamic, Eytan Adar
It is shown that some factors are better indicators of social connections than others, and that these indicators vary between user populations.
Philosophical Transactions of the Royal Society of LondonLII. An essay towards solving a problem in the doctrine of chances. By the late Rev. Mr. Bayes, F. R. S. communicated by Mr. Price, in a letter to John Canton, A. M. F. R. S
2,873 Citations1763Thomas Bayes
IEEE Circuits and Systems MagazineEnsemble based systems in decision making
2,866 Citations2006Robi Polikar
Conditions under which ensemble based systems may be more beneficial than their single classifier counterparts are reviewed, algorithms for generating individual components of the ensemble systems, and various procedures through which the individual classifiers can be combined are reviewed.
Social NetworksStochastic blockmodels: First steps
2,855 Citations1983Paul W. Holland, Kathryn Blackmond Laskey +1 more
Estimation techniques are developed for the special case of a single relation social network, with blocks specified a priori, and an extension of the model allows for tendencies toward reciprocation of ties beyond those explained by the partition.
Advances In PhysicsCharacterization of complex networks: A survey of measurements
2,456 Citations2007Luciano da Fontoura Costa, Francisco A. Rodrigues +2 more
This article presents a survey of measurements capable of expressing the most relevant topological features of complex networks and includes general considerations about complex network characterization, a brief review of the principal models, and the presentation of the main existing measurements.
Physical Review EAnalysis of weighted networks
2,451 Citations2004M. E. J. Newman
It is pointed out that weighted networks can in many cases be analyzed using a simple mapping from a weighted network to an unweighted multigraph, allowing us to apply standard techniques for unweighting graphs to weighted ones as well.
Random Structures and AlgorithmsA critical point for random graphs with a given degree sequence
2,401 Citations1995Michael Molloy, Bruce Reed
It is shown that if Σ i(i - 2)λi > 0, then such graphs almost surely have a giant component, while if λ0, λ1… which sum to 1, then almost surely all components in such graphs are small.
NatureComparative assessment of large-scale data sets of protein–protein interactions
2,377 Citations2002Christian von Mering, Roland Krause +5 more
Comprehensive protein–protein interaction maps promise to reveal many aspects of the complex regulatory network underlying cellular function and are compared with each other and with a reference set of previously reported protein interactions.
The American StatisticianExplaining the Gibbs Sampler
2,355 Citations1992George Casella, Edward I. George
A simple explanation of how and why the Gibbs sampler works is given and analytically establish its properties in a simple case and insight is provided for more complicated cases.
Behavioral Ecology and SociobiologyThe bottlenose dolphin community of Doubtful Sound features a large proportion of long-lasting associations
2,279 Citations2003David Lusseau, Karsten Schneider +4 more
A small, closed population of bottlenose dolphins living at the southern extreme of the species' range is described, which hypothesise that ecological constraints are important factors shaping social interactions within cetacean societies.
NatureHierarchical structure and the prediction of missing links in networks
2,198 Citations2008Aaron Clauset, Cristopher Moore +1 more
This work presents a general technique for inferring hierarchical structure from network data and shows that the existence of hierarchy can simultaneously explain and quantitatively reproduce many commonly observed topological properties of networks.
American Journal of SociologySocial Structure from Multiple Networks. I. Blockmodels of Roles and Positions
2,050 Citations1976Harrison C. White, Scott A. Boorman +1 more
Physical review. E, Statistical physics, plasmas, fluids, and related interdisciplinary topicsClustering and preferential attachment in growing networks
2,047 Citations2001M. E. J. Newman
It is shown that the probability of a pair of scientists collaborating increases with the number of other collaborators they have in common, and that the probabilities of a particular scientist acquiring new collaborators increases withThe number of his or her past collaborators.
Machine LearningLearning Bayesian networks: The combination of knowledge and statistical data
2,043 Citations1995David Heckerman, Dan Geiger +1 more
It is shown that likelihood equivalence when combined with previously made assumptions implies that the user's priors for network parameters can be encoded in a single Bayesian network for the next case to be seen—aprior network—and a single measure of confidence for that network.
SimRank
1,938 Citations2002Glen Jeh, Jennifer Widom
A complementary approach, applicable in any domain with object-to-object relationships, that measures similarity of the structural context in which objects occur, based on their relationships with other objects is proposed.
Physical review. E, Statistical physics, plasmas, fluids, and related interdisciplinary topicsAttack vulnerability of complex networks
1,835 Citations2002Petter Holme, Beom Jun Kim +2 more
It is found that the removals by the recalculated degrees and betweenness centralities are often more harmful than the attack strategies based on the initial network, suggesting that the network structure changes as important vertices or edges are removed.
The European Physical Journal BPredicting missing links via local information
1,828 Citations2009Tao Zhou, Linyuan Lü +1 more
A new similarity measure, motivated by the resource allocation process taking place on networks, is proposed and shown to have higher prediction accuracy than common neighbours, which can remarkably enhance the prediction accuracy.
Proceedings of the National Academy of SciencesThe worldwide air transportation network: Anomalous centrality, community structure, and cities' global roles
1,780 Citations2005Roger Guimerà, Stefano Mossa +2 more
It is found that the worldwide air transportation network is a scale-free small-world network, and it is demonstrated that the most connected cities are not necessarily the most central, resulting in anomalous values of the centrality.
Physical Review LettersSynchronization in Small-World Systems
1,603 Citations2002Mauricio Barahona, Louis M. Pecora
Applied to networks of low redundancy, the small-world route produces synchronizability more efficiently than standard deterministic graphs, purely random graphs, and ideal constructive schemes.
Springer series in statisticsIntroduction to Metropolis, Rosenbluth, Rosenbluth, Teller, and Teller (1953) Equations of State Calculations by Fast Computing Machines. J. Chem. Phys.,21, 1087–1092. and Geman and Geman (1984) Stochastic Relaxation, Gibbs Distributions, and the Bayesian Restoration of Images. IEEE Trans. Pattern Anal. Machine Intelligence,6, 721–741.
1,550 Citations1997Peter J. Huber
PubMedMixed Membership Stochastic Blockmodels.
1,526 Citations2008Edoardo M. Airoldi, David M. Blei +2 more
This paper describes a latent variable model of such data called the mixed membership stochastic blockmodel, which extends blockmodels for relational data to ones which capture mixed membership latent relational structure, thus providing an object-specific low-dimensional representation.
Data Mining and Knowledge DiscoveryE-Commerce Recommendation Applications
1,518 Citations2001J. Ben Schafer, Joseph A. Konstan +1 more
An explanation of how recommender systems are related to some traditional database analysis techniques is presented, and a taxonomy ofRecommender systems is created, including the inputs required from the consumers, the additional knowledge required from a database, the ways the recommendations are presented to consumers,The technologies used to create the recommendations, and the level of personalization of the recommendations.
Propagation of trust and distrust
1,471 Citations2004R. Guha, Ravi Kumar +2 more
It is shown that a small number of expressed trusts/distrust per individual allows us to predict trust between any two people in the system with high accuracy.
Predicting positive and negative links in online social networks
1,454 Citations2010Jure Leskovec, Daniel P. Huttenlocher +1 more
These models provide insight into some of the fundamental principles that drive the formation of signed links in networks, shedding light on theories of balance and status from social psychology and suggest social computing applications by which the attitude of one user toward another can be estimated from evidence provided by their relationships with other members of the surrounding social network.
Physical Review LettersDynamical and Correlation Properties of the Internet
1,452 Citations2001Romualdo Pastor‐Satorras, Alexei Vázquez +1 more
It is found that the Internet is characterized by non-trivial correlations among nodes and different dynamical regimes, and the importance of node hierarchy and aging in the Internet structure and growth is pointed out.
ScienceHigh-Quality Binary Protein Interaction Map of the Yeast Interactome Network
1,428 Citations2008Haiyuan Yu, Pascal Falter‐Braun +32 more
A comparative quality assessment of current yeast interactome data sets is carried out, demonstrating that high-throughput yeast two-hybrid (Y2H) screening provides high-quality binary interaction information.
Journal of Mathematical ChemistryResistance distance
1,352 Citations1993Douglas J. Klein, Milan Randić
IEEE Transactions on Knowledge and Data EngineeringRandom-Walk Computation of Similarities between Nodes of a Graph with Application to Collaborative Recommendation
1,261 Citations2007François Fouss, Alain Pirotte +2 more
The model, which nicely fits into the so-called "statistical relational learning" framework, could also be used to compute document or word similarities, and could be applied to machine-learning and pattern-recognition tasks involving a relational database.
ProceedingsFast Random Walk with Restart and Its Applications
1,209 Citations2006Hanghang Tong, Christos Faloutsos +1 more
The heart of the approach is to exploit two important properties shared by many real graphs: linear correlations and block- wise, community-like structure and exploit the linearity by using low-rank matrix approximation, and the community structure by graph partitioning, followed by the Sherman- Morrison lemma for matrix inversion.
Physical Review EBipartite network projection and personal recommendation
1,074 Citations2007Tao Zhou, Jie Ren +2 more
This work provides a creditable method for compressing bipartite networks, and highlights a possible way for the better solution of a long-standing challenge in modern information science: How to do a personal recommendation.
Nature PhysicsDetecting rich-club ordering in complex networks
1,021 Citations2006Vittoria Colizza, Alessandro Flammini +2 more
The presented analysis enables the measurement of the rich-club ordering and its relation with the function and dynamics of networks in examples drawn from the biological, social and technological domains.
Genome biologyAn expanded genome-scale model of Escherichia coli K-12 (iJR904 GSM/GPR)
1,020 Citations2003Jennifer L. Reed, Thuy D. Vo +2 more
iJR904 will help to outline the genotype-phenotype relationship for E. coli K-12, as it can account for genomic, transcriptomic, proteomic and fluxomic data simultaneously, and has improved capabilities over iJE660a.
IEEE/ACM Transactions on NetworkingMeasuring ISP Topologies With Rocketfuel
1,014 Citations2004Neil Spring, Ratul Mahajan +2 more
New Internet mapping techniques that have enabled us to measure router-level ISP topologies are presented, finding that these maps are substantially more complete than those of earlier Internet mapping efforts.
Mapping Networks of Terrorist Cells
980 Citations2001Valdis Krebs
The network surrounding the tragic events of September 11th, 2001 is examined, and through public data, a portion of the network centered around the 19 dead hijackers is mapped.
ACM SIGKDD Explorations NewsletterLink mining
977 Citations2005Lise Getoor, Christopher Diehl
While network analysis has been studied in depth in particular areas such as social network analysis, hypertext mining, and web analysis, only recently has there been a cross-fertilization of ideas among these different communities.
Proceedings of the National Academy of SciencesSolving the apparent diversity-accuracy dilemma of recommender systems
970 Citations2010Tao Zhou, Zoltán Kuscsik +4 more
This paper introduces a new algorithm specifically to address the challenge of diversity and shows how it can be used to resolve this apparent dilemma when combined in an elegant hybrid with an accuracy-focused algorithm.
Journal of The Royal Society InterfaceThe complex network of global cargo ship movements
956 Citations2010Pablo Kaluza, Andrea Kölzsch +2 more
The data analysed in this paper improve current assumptions based on gravity models of ship movements, an important step towards understanding patterns of global trade and bioinvasion.
Proceedings of the National Academy of SciencesMultirelational organization of large-scale social networks in an online world
956 Citations2010Michael Szell, Renaud Lambiotte +1 more
This work presents the first empirical large-scale verification of the long-standing structural balance theory, by focusing on the specific multiplex network of friendship and enmity relations, and explores how the interdependence of different network types determines the organization of the social system.
Handbook of Graphs and Networks
945 Citations2002Stefan Bornholdt, Heinz Georg Schuster
This book defines the field of complex interacting networks in its infancy and presents the dynamics of networks and their structure as a key concept across disciplines and offers concepts to model network structures and dynamics, focussed on approaches applicable across disciplines.
Learning Probabilistic Relational Models
941 Citations2001Lise Getoor, Nir Friedman +2 more
Physical Review EVertex similarity in networks
914 Citations2006E. A. Leicht, Petter Holme +1 more
A measure of similarity based on the concept that two vertices are similar if their immediate neighbors in the network are themselves similar is proposed, which leads to a self-consistent matrix formulation of similarity that can be evaluated iteratively using only a knowledge of the adjacency matrix of the network.
Social NetworksEffects of missing data in social networks
896 Citations2005Gueorgi Kossinets
It is found that social networks with multiple interaction contexts may have certain interesting properties due to the presence of overlapping cliques, and assortativity by degree does not necessarily improve network robustness to random omission of nodes as predicted by current theory.
Proceedings of the National Academy of SciencesEstimating the size of the human interactome
824 Citations2008Michael P. H. Stumpf, Thomas Thorne +5 more
It is found that the human interaction network is one order of magnitude bigger than the Drosophila melanogaster interactome and ≈3 times bigger than in Caenorhabditis elegans.
Proceedings of the National Academy of SciencesMissing and spurious interactions and the reconstruction of complex networks
812 Citations2009Roger Guimerà, Marta Sales‐Pardo
This work is able to reliably identify both missing and spurious interactions in noisy network observations and enables network reconstructions that yield estimates of the true network properties that are more accurate than those provided by the observations themselves.
Physical Review LettersScale-Free Networks from Varying Vertex Intrinsic Fitness
786 Citations2002Guido Caldarelli, Andrea Capocci +2 more
A new mechanism leading to scale-free networks is proposed, which is called a good-get-richer mechanism, in which sites with larger fitness are more likely to become hubs (i.e., to be highly connected).
arXiv (Cornell University)Mixed membership stochastic blockmodels
786 Citations2007Edoardo M. Airoldi, David M. Blei +2 more
Proceedings of the National Academy of SciencesA model of Internet topology using <i>k</i> -shell decomposition
771 Citations2007Shai Carmi, Shlomo Havlin +3 more
This analysis uses information on the connectivity of the network shells to separate, in a unique (no parameters) way, the Internet into three subcomponents: a nucleus that is a small, very well connected globally distributed subgraph; a fractal subcomponent that is able to connect the bulk of the Internet without congesting the nucleus, with self-similar properties and critical exponents predicted from percolation theory.
Physical review. E, Statistical physics, plasmas, fluids, and related interdisciplinary topicsLarge-scale topological and dynamical properties of the Internet
691 Citations2002Alexei Vázquez, Romualdo Pastor‐Satorras +1 more
It is found that the connectivity structure of the Internet presents statistical distributions settled in a well-defined stationary state and the large-scale properties are characterized by a scale-free topology consistent with previous observations.
International Statistical ReviewSubmodel Selection and Evaluation in Regression. The X-Random Case
670 Citations1992Leo Breiman, Philip C. Spector
Physical Review ESimilarity index based on local paths for link prediction of complex networks
665 Citations2009Linyuan Lü, Ci-Hang Jin +1 more
A local path index is introduced to estimate the likelihood of the existence of a link between two nodes and provides competitively accurate predictions as the Katz index while requires much less CPU time and memory space, which makes it a strong candidate for potential practical applications in data mining of huge-size networks.
Physical Review EEfficient routing on complex networks
631 Citations2006Gang Yan, Tao Zhou +3 more
A generalized routing algorithm is given to find the so-called efficient path, which considers the possible congestion in the nodes along actual paths, to improve the transportation efficiency on complex networks.
IEEE Communications LettersThe Rich-Club Phenomenon in the Internet Topology
627 Citations2004Shi Zhou, Raúl J. Mondragón
It is shown that the Internet topology at the autonomous system (AS) level has a rich-club phenomenon, which is a simple qualitative way to differentiate between power law topologies and provides a criterion for new network models.
Physical Review LettersOptimal Network Topologies for Local Search with Congestion
601 Citations2002Roger Guimerà, Albert Dı́az-Guilera +3 more
A formalism is presented that is able to cope simultaneously with the problem of search and the congestion effects that arise when parallel searches are performed, and expressions for the average search cost are obtained both in the presence and the absence of congestion.
Predictive Inference
574 Citations2017Martin Lawera
Europhysics Letters (EPL)Link prediction based on local random walk
571 Citations2010Weiping Liu, Linyuan Lü
This letter proposed a method based on local random walk, which can give competitively good or even better prediction than other random-walk–based methods while having a much lower computational complexity.
Proceedings of the National Academy of SciencesExtracting the hierarchical organization of complex systems
552 Citations2007Marta Sales‐Pardo, Roger Guimerà +2 more
An unsupervised method for extracting the hierarchical organization of complex biological, social, and technological networks is introduced and validated and an ensemble of hierarchically nested random graphs is defined, which is used to validate the method.
Journal of Artificial Intelligence ResearchOperations for Learning with Graphical Models
538 Citations1994Wray Buntine
The main original contributions here are the decompositiontechniques and the demonstration that graphical models provide a framework for understanding and developing complex learning algorithms.
Physical Review LettersHierarchical Organization Unveiled by Functional Connectivity in Complex Brain Networks
512 Citations2006Changsong Zhou, Lucia Zemanová +3 more
This work study synchronization dynamics in the cortical brain network of the cat finds that in the biologically plausible regime the dynamics exhibits a hierarchical modular organization, in particular, revealing functional clusters coinciding with the anatomical communities at different scales.
The European Physical Journal BThe spatial structure of networks
480 Citations2006Michael T. Gastner, M. E. J. Newman
There are strong signatures in these networks of topography and use patterns, giving the networks shapes that are quite distinct from one another and from non-geographic networks.
Cambridge University Press eBooksGeneralized Blockmodeling
470 Citations2004Patrick Doreian, Vladimir Batagelj +1 more
Physica A Statistical Mechanics and its ApplicationsGeographical dispersal of mobile communication networks
447 Citations2008Renaud Lambiotte, Vincent D. Blondel +5 more
It is shown that the degree distribution in this network has a power-law degree distribution k−5 and that the probability that two customers are connected by a link follows a gravity model, i.e. decreases as d−2, where d is the distance between the customers.
…