BZPEERPapers, people, evidence and research pathsDiscover
Research tools
Network
Opportunities
Account
Source author record
Yi Tang appears in the imported research catalog. Authorship, coauthor and topic links are available while profile ownership is still unclaimed.
Catalog footprint
Research graph
Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.
BZPEER is loading the nearby papers, people, topics and institutions for this page.
Published work
We show that for any $n$-dimensional lattice $\mathcal{L} \subseteq \mathbb{R}^n$, the torus $\mathbb{R}^n/\mathcal{L}$ can be embedded into Hilbert space with $O(\sqrt{n\log n})$ distortion. This improves the previously best known upper bound of $O(n\sqrt{\log n})$ shown by Haviv and Regev (APPROX 2010) and approaches the lower bound of $Ω(\sqrt{n})$ due to Khot and Naor (FOCS 2005, Math. Annal. 2006).
Many algorithms have been proposed to predict missing links in a variety of real networks. These studies focus on mainly both accuracy and efficiency of these algorithms. However, little attention is paid to their robustness against either noise or irrationality of a link existing in almost all of real networks. In this paper, we investigate the robustness of several typical node-similarity-based algorithms and find that these algorithms are sensitive to the strength of noise. Moreover, we find that it also depends on networks' structure properties, especially on network efficiency, clustering coefficient and average degree. In addition, we make an attempt to enhance the robustness by using link weighting method to transform un-weighted network to weighted one and then make use of weights of links to characterize their reliability. The result shows that proper link weighting scheme can enhance both robustness and accuracy of these algorithms significantly in biological networks while it brings little computational effort.
In principle, the rules of links formation of a network model can be considered as a kind of link prediction algorithm. By revisiting the preferential attachment mechanism for generating a scale-free network, here we propose a class of preferential attachment indices which are different from the previous one. Traditionally, the preferential attachment index is defined by the product of the related nodes degrees, while the new indices will define the similarity score of a pair of nodes by either the maximum in the two nodes degrees or the summarization of their degrees. Extensive experiments are carried out on fourteen real-world networks. Compared with the traditional preferential attachment index, the new ones, especially the degree-summarization similarity index, can provide more accurate prediction on most of the networks. Due to the improved prediction accuracy and low computational complexity, these proposed preferential attachment indices may be of help to provide an instruction for mining unknown links in incomplete networks.
Evolving network models under a dynamic growth rule which comprises the addition and deletion of nodes are investigated. By adding a node with a probability $P_a$ or deleting a node with the probability $P_d=1-P_a$ at each time step, where $P_a$ and $P_d$ are determined by the Logistic population equation, topological properties of networks are studied. All the fat-tailed degree distributions observed in real systems are obtained, giving the evidence that the mechanism of addition and deletion can lead to the diversity of degree distribution of real systems. Moreover, it is found that the networks exhibit nonstationary degree distributions, changing from the power-law to the exponential one or from the exponential to the Gaussian one. These results can be expected to shed some light on the formation and evolution of real complex real-world networks.
The basic idea of many effective immunization strategies is first to rank the importance of vertices according to the degrees of vertices and then remove the vertices from highest importance to lowest until the network becomes disconnected. Here we define the effective degrees of vertex, i.e., the number of its connections linking to un-immunized nodes in current network during the immunization procedure, to rank the importance of vertex, and modify these strategies by using the effective degrees of vertices. Simulations on both the scale-free network models with various degree correlations and two real networks have revealed that the immunization strategies based on the effective degrees are often more effective than those based on the degrees in the initial network.