Search

The organization of real networks usually embodies both regularities and irregularities, and, in principle, the former can be modeled. The extent to which the formation of a network can be explained coincides with our ability to predict missing links. To understand network organization, we should be able to estimate link predictability. We assume that the regularity of a network is reflected in the consistency of structural features before and after a random removal of a small set of links. Based on the perturbation of the adjacency matrix, we propose a universal structural consistency index that is free of prior knowledge of network organization. Extensive experiments on disparate realworld networks demonstrate that (i) structural consistency is a good estimation of link predictability and (ii) a derivative algorithm outperforms state-of-the-art link prediction methods in both accuracy and robustness. This analysis has further applications in evaluating link prediction algorithms and monitoring sudden changes in evolving network mechanisms. It will provide unique fundamental insights into the above-mentioned academic research fields, and will foster the development of advanced information filtering technologies of interest to information technology practitioners. [ABSTRACT FROM AUTHOR]

Some epidemic spreading models are usually applied to analyze the propagation of opinions or news. However, the dynamics of epidemic spreading and information or behavior spreading are essentially different in many aspects. Centola's experiments [Science 329, 1194 (2010)] on behavior spreading in online social networks showed that the spreading is faster and broader in regular networks than in random networks. This result contradicts with the former understanding that random networks are preferable for spreading than regular networks. To describe the spreading in online social networks, a unknown-known-approved-exhausted four-status model was proposed, which emphasizes the effect of social reinforcement and assumes that the redundant signals can improve the probability of approval (i.e., the spreading rate). Performing the model on regular and random networks, it is found that our model can well explain the results of Centola's experiments on behavior spreading and some former studies on information spreading in different parameter space. The effects of average degree and network size on behavior spreading process are further analyzed. The results again show the importance of social reinforcement and are accordant with Centola's anticipation that increasing the network size or decreasing the average degree will enlarge the difference of the density of final approved nodes between regular and random networks. Our work complements the former studies on spreading dynamics, especially the spreading in online social networks where the information usually requires individuals' confirmations before being transmitted to others [ABSTRACT FROM AUTHOR]

In this paper, we studied the strategies to enhance synchronization on directed networks by manipulating a fixed number of links. We proposed a centrality-based manipulating (CBM) method, where the node centrality is measured by the well-known PageRank algorithm. Extensive numerical simulation on many modeled networks demonstrated that the CBM method is more effective in facilitating synchronization than the degree-based manipulating method and the random manipulating method for adding or removing links. The reason is that the CBM method can effectively narrow the incoming degree distribution and reinforce the hierarchical structure of the network. Furthermore, we apply the CBM method to the links rewiring procedure where at each step one link is removed and one new link is added. The CBM method helps to decide which links should be removed or added. After several steps, the resulting networks are very close to the optimal structure from the theoretical analysis and the evolutionary optimization algorithm. The numerical simulations on the Kuramoto model further demonstrate that our method has an advantage in shortening the convergence time to synchronization on directed networks. [ABSTRACT FROM AUTHOR]

The number of citations is a widely used metric for evaluating the scientific credit of papers, scientists and journals. However, it so happens that papers with fewer citations from prestigious scientists have a higher influence than papers with more citations. In this paper, we argue that by whom the paper is being cited is of greater significance than merely the number of citations. Accordingly, we propose an interactive model of author-paper bipartite networks as well as an iterative algorithm to obtain better rankings for scientists and their publications. The main advantage of this method is twofold: (i) it is a parameter-free algorithm; (ii) it considers the relationship between the prestige of scientists and the quality of their publications.We conducted real experiments on publications in econophysics, and used this method to evaluate the influence of related scientific journals. The comparison between the rankings by our method and simple citation counts suggests that our method is effective in distinguishing prestige from popularity. [ABSTRACT FROM AUTHOR]

The spreading dynamics of information and diseases are usually analyzed by using a unified framework and analogous models. In this paper, we propose a model to emphasize the essential difference between information spreading and epidemic spreading, where the memory effects, the social reinforcement and the non-redundancy of contacts are taken into account. Under certain conditions, the information spreads faster and broader in regular networks than in random networks, which to some extent supports the recent experimental observation of spreading in online society (Centola D 2010 Science 329 1194). At the same time, the simulation result indicates that the random networks tend to be favorable for effective spreading when the network size increases. This challenges the validity of the above-mentioned experiment for large-scale systems. More importantly, we show that the spreading effectiveness can be sharply enhanced by introducing a little randomness into the regular structure, namely the small-world networks yield the most effective information spreading. This work provides insights into the role of local clustering in information spreading. [ABSTRACT FROM AUTHOR]

Recommender systems have shown great potential in addressing the information overload problem, namely helping users in finding interesting and relevant objects within a huge information space. Some physical dynamics, including the heat conduction process and mass or energy diffusion on networks, have recently found applications in personalized recommendation. Most of the previous studies focus overwhelmingly on recommendation accuracy as the only important factor, while overlooking the significance of diversity and novelty that indeed provide the vitality of the system. In this paper, we propose a recommendation algorithm based on the preferential diffusion process on a user-object bipartite network. Numerical analyses on two benchmark data sets, MovieLens and Netflix, indicate that our method outperforms the state-of-the-art methods. Specifically, it can not only provide more accurate recommendations, but also generate more diverse and novel recommendations by accurately recommending unpopular objects. [ABSTRACT FROM AUTHOR]

Finding pertinent information is not limited to search engines. Online communities can amplify the influence of a small number of power users for the benefit of all other users. Users' information foraging in depth and breadth can be greatly enhanced by choosing suitable leaders. For instance in delicious.com, users subscribe to leaders' collection which lead to a deeper and wider reach not achievable with search engines. To consolidate such collective search, it is essential to utilize the leadership topology and identify influential users. Google's PageRank, as a successful search algorithm in the World Wide Web, turns out to be less effective in networks of people. We thus devise an adaptive and parameter-free algorithm, the LeaderRank, to quantify user influence. We show that LeaderRank outperforms PageRank in terms of ranking effectiveness, as well as robustness against manipulations and noisy data. These results suggest that leaders who are aware of their clout may reinforce the development of social networks, and thus the power of collective search. [ABSTRACT FROM AUTHOR]

Background: Zipf's law and Heaps' law are observed in disparate complex systems. Of particular interests, these two laws often appear together. Many theoretical models and analyses are performed to understand their co-occurrence in real systems, but it still lacks a clear picture about their relation. Methodology/Principal Findings: We show that the Heaps' law can be considered as a derivative phenomenon if the system obeys the Zipf's law. Furthermore, we refine the known approximate solution of the Heaps' exponent provided the Zipf's exponent. We show that the approximate solution is indeed an asymptotic solution for infinite systems, while in the finite-size system the Heaps' exponent is sensitive to the system size. Extensive empirical analysis on tens of disparate systems demonstrates that our refined results can better capture the relation between the Zipf's and Heaps' exponents. Conclusions/Significance: The present analysis provides a clear picture about the relation between the Zipf's law and Heaps' law without the help of any specific stochastic model, namely the Heaps' law is indeed a derivative phenomenon from the Zipf's law. The presented numerical method gives considerably better estimation of the Heaps' exponent given the Zipf's exponent and the system size. Our analysis provides some insights and implications of real complex systems. For example, one can naturally obtained a better explanation of the accelerated growth of scale-free networks. [ABSTRACT FROM AUTHOR]

We consider a simple market where a vendor offers multiple variants of a certain product and preferences of both the vendor and potential buyers are heterogeneous and possibly even antagonistic. Optimization of the joint benefit of the vendor and the buyers turns the toy market into a combinatorial matching problem. We compare the optimal solutions found with and without a matchmaker, examine the resulting inequality between the market participants, and study the impact of correlations on the system. [ABSTRACT FROM AUTHOR]

Missing link prediction in networks is of both theoretical interest and practical significance in modern science. In this paper, we empirically investigate a simple framework of link prediction on the basis of node similarity. We compare nine well-known local similarity measures on six real networks. The results indicate that the simplest measure, namely Common Neighbours, has the best overall performance, and the Adamic-Adar index performs second best. 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. It is found that many links are assigned the same scores if only the information of the nearest neighbours is used. We therefore design another new measure exploiting information on the next nearest neighbours, which can remarkably enhance the prediction accuracy. [ABSTRACT FROM AUTHOR]

Keywords in scientific articles have found their significance in information filtering and classification. In this article, we empirically investigated statistical characteristics and evolutionary properties of keywords in a very famous journal, namely Proceedings of the National Academy of Science of the United States of America (PNAS), including frequency distribution, temporal scaling behavior, and decay factor. The empirical results indicate that the keyword frequency in PNAS approximately follows a Zipf’s law with exponent 0.86. In addition, there is a power-low correlation between the cumulative number of distinct keywords and the cumulative number of keyword occurrences. Extensive empirical analysis on some other journals’ data is also presented, with decaying trends of most popular keywords being monitored. Interestingly, top journals from various subjects share very similar decaying tendency, while the journals of low impact factors exhibit completely different behavior. Those empirical characters may shed some light on the in-depth understanding of semantic evolutionary behaviors. In addition, the analysis of keyword-based system is helpful for the design of corresponding recommender systems. [ABSTRACT FROM AUTHOR]

Social networks constitute a new platform for information propagation, but its success is crucially dependent on the choice of spreaders who initiate the spreading of information. In this paper, we remove edges in a network at random and the network segments into isolated clusters. The most important nodes in each cluster then form a set of influential spreaders, such that news propagating from them would lead to extensive coverage and minimal redundancy. The method utilizes the similarities between the segmented networks before percolation and the coverage of information propagation in each social cluster to obtain a set of distributed and coordinated spreaders. Our tests of implementing the susceptible-infected-recovered model on Facebook and Enron email networks show that this method outperforms conventional centrality-based methods in terms of spreadability and coverage redundancy. The suggested way of identifying influential spreaders thus sheds light on a new paradigm of information propagation in social networks. [ABSTRACT FROM AUTHOR]

The advent of the Internet and World Wide Web has led to unprecedent growth of the information available. People usually face the information overload by following a limited number of sources which best fit their interests. It has thus become important to address issues like who gets followed and how to allow people to discover new and better information sources. In this paper we conduct an empirical analysis of different online social networking sites and draw inspiration from its results to present different source selection strategies in an adaptive model for social recommendation. We show that local search rules which enhance the typical topological features of real social communities give rise to network configurations that are globally optimal. These rules create networks which are effective in information diffusion and resemble structures resulting from real social systems. [ABSTRACT FROM AUTHOR]

Recommender systems are becoming a popular and important set of personalization techniques that assist individual users with navigating through the rapidly growing amount of information. A good recommender system should be able to not only find out the objects preferred by users, but also help users in discovering their personalized tastes. The former corresponds to high accuracy of the recommendation, while the latter to high diversity. A big challenge is to design an algorithm that provides both highly accurate and diverse recommendation. Traditional recommendation algorithms only take into account the contributions of similar users, thus, they tend to recommend popular items for users ignoring the diversity of recommendations. In this paper, we propose a recommendation algorithm by considering both the effects of similar and dissimilar users under the framework of collaborative filtering. Extensive analyses on three datasets, namely MovieLens, Netflix and Amazon, show that our method performs much better than the standard collaborative filtering algorithm for both accuracy and diversity. [ABSTRACT FROM AUTHOR]