  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.
