Link prediction is the problem of predicting the location of either unknown or fake links from uncertain structural information of a network. Link prediction algorithms are useful in gaining insight into different network structures from partial observations of exemplars. However, existing link prediction algorithms only focus on regular complex networks and are overly dependent on either the closed triangular structure of networks or the so-called preferential attachment phenomenon. The performance of these algorithms on highly sparse or treelike networks is poor. In this letter, we proposed a method that is based on the network heterogeneity. We test our algorithms for three real large sparse networks: a metropolitan water distribution network, a Twitter network, and a sexual contact network. We find that our method is effective and performs better than traditional algorithms, especially for the Twitter network. We further argue that heterogeneity is the most obvious defining pattern for complex networks, while other statistical properties failed to be predicted. Moreover, preferential attachment based link prediction performed poorly and hence we infer that preferential attachment is not a plausible model for the genesis of many networks. We also suggest that heterogeneity is an important mechanism for online information propagation.

Evolution and popularity are two keys of the Barabasi–Albert model, which generates a power law distribution of network degrees. Evolving network generation models are important as they offer an explanation of both how and why complex networks (and scale-free networks, in particular) are ubiquitous. We adopt the evolution principle and then propose a very simple and intuitive new model for network growth, which naturally evolves modular networks with multiple communities. The number and size of the communities evolve over time and are primarily subjected to a single free parameter. Surprisingly, under some circumstances, our framework can construct a tree-like network with clear community structures—branches and leaves of a tree. Results also show that new communities will absorb a link resource to weaken the degree growth of hub nodes. Our models have a common explanation for the community of regular and tree-like networks and also breaks the tyranny of the early adopter; unlike the standard popularity principle, newer nodes and communities will come to dominance over time. Importantly, our model can fit well with the construction of the SARS-Cov-2 haplotype evolutionary network.

Link prediction is the problem of predicting the uncertain relationship between a pair of nodes from observed structural information of a network. Link prediction algorithms are useful in gaining insight into different network structures from partial observation of exemplars. Existing local and quasilocal link prediction algorithms with low computational complexity focus on regular complex networks with sufficiently many closed triangular motifs or on tree-like networks with the vast majority of open triangular motifs. However, the three-node motif cannot describe the local structural features of all networks, and we find the main structure of many networks is long line or closed circle that cannot be predicted well via traditional link prediction algorithms. Meanwhile, some global link prediction algorithms are effective but accompanied by high computational complexity. In this paper, we proposed a local method that is based on the natural characteristic of a long line—in contrast to the preferential attachment principle. Next, we test our algorithms for two kinds of symbolic long-circle-like networks: a metropolitan water distribution network and a sexual contact network. We find that our method is effective and performs much better than many traditional local and global algorithms. We adopt the community detection method to improve the accuracy of our algorithm, which shows that the long-circle-like networks also have clear community structure. We further suggest that the structural features are key for the link prediction problem. Finally, we propose a long-line network model to prove that our core idea is of universal significance.