The prediction of graph evolution is an important and challenging problem in the analysis of networks and of the Web in particular. But while the appearance of new links is part of virtually every model of Web growth, the disappearance of links has received much less attention in the literature. To fill this gap, our approach DecLiNe (an acronym for DECay of LInks in NEtworks) aims to predict link decay in networks, based on structural analysis of corresponding graph models. In analogy to the link prediction problem, we show that analysis of graph structures can help to identify indicators for superfluous links under consideration of common network models. In doing so, we introduce novel metrics that denote the likelihood of certain links in social graphs to remain in the network, and combine them with state-of-the-art machine learning methods for predicting link decay. Our methods are independent of the underlying network type, and can be applied to such diverse networks as the Web, social networks and any other structure representable as a network, and can be easily combined with case-specific content analysis and adopted for a variety of social network mining, filtering and recommendation applications. In systematic evaluations with large-scale datasets of Wikipedia we show the practical feasibility of the proposed structure-based link decay prediction algorithms.
Several graph growth models include link disappearance in addition to link creation, for instance in a model to explain power laws @cite_26 . Other examples can be found in @cite_0 and @cite_3 , in which a model for growth of the Web is given in which edges are removed before others are added. While these methods succeed in predicting global characteristics of networks such as the degree distribution, they do not model the structure of the network, and thus cannot be used for predicting individual links.
@cite_0 @cite_26 @cite_3
2963605078 2112566225 2129620481
Power law distribution seems to be an important characteristic of web graphs. Several existing web graph models generate power law graphs by adding new vertices and non-uniform edge connectivities to existing graphs. Researchers have conjectured that preferential connectivity and incremental growth are both required for the power law distribution. In this paper, we propose a different web graph model with power law distribution that does not require incremental growth. We also provide a comparison of our model with several others in their ability to predict web graph clustering behavior. We investigate the general conditions under which power laws emerge in networks for the degree distributions (the number of links a node has). Our study is based on a new and versatile random-walk network model (the exciton model) that includes all processes of link creation, link removal, node creation and node loss. From the principle of detailed balance simple 'litmus' test criteria for the emergence of power laws are derived. Results are compared with existing models in the network science literature, and we show how they can be generalized. An important result is that there is a very broad set of conditions under which power laws will emerge, among them nonlinearity in network formation. We show that power laws may be explained purely as a mesoscopic statistical phenomenon, on the basis of the scale-free network statistics assumption of equiprobability of existing nodes plus links. Hence, explanations rooted in making (microscopic) assumptions about individual preferences or behaviour can be avoided. The causal mechanism underlying this scale-free network statistics is, we suggest, the social and self-reinforcing mechanism of information feedback to network actors about structure and status of the network itself. The pages and hyperlinks of the World-Wide Web may be viewed as nodes and edges in a directed graph. This graph is a fascinating object of study: it has several hundred million nodes today, over a billion links, and appears to grow exponentially with time. There are many reasons -- mathematical, sociological, and commercial -- for studying the evolution of this graph. In this paper we begin by describing two algorithms that operate on the Web graph, addressing problems from Web search and automatic community discovery. We then report a number of measurements and properties of this graph that manifested themselves as we ran these algorithms on the Web. Finally, we observe that traditional random graph models do not explain these observations, and we propose a new family of random graph models. These models point to a rich new sub-field of the study of random graphs, and raise questions about the analysis of graph algorithms on the Web.