Abstract
We investigate the structural patterns of the appearance and disappearance of links in dynamic knowledge networks. Human knowledge is nowadays increasingly created and curated online, in a collaborative and highly dynamic fashion. The knowledge thus created is interlinked in nature, and an important open task is to understand its temporal evolution. In this paper, we study the underlying mechanisms of changes in knowledge networks which are of structural nature, i.e., which are a direct result of a knowledge network's structure. Concretely, we ask whether the appearance and disappearance of interconnections between concepts (items of a knowledge base) can be predicted using information about the network formed by these interconnections. In contrast to related work on this problem, we take into account the disappearance of links in our study, to account for the fact that the evolution of collaborative knowledge bases includes a high proportion of removals and reverts. We perform an empirical study on the best-known and largest collaborative knowledge base, Wikipedia, and show that traditional indicators of structural change used in the link analysis literature can be classified into four classes, which we show to indicate growth, decay, stability and instability of links. We finally use these methods to identify the underlying reasons for individual additions and removals of knowledge links.
Introduction
Most research in link prediction focuses exclusively on network growth: predicting which new connections will form. However, in collaborative environments like Wikipedia, the "death" of a link is a frequent and significant event. Between 20% and 30% of Wikipedia edits involve removing or reverting links. To truly understand the structural dynamics of knowledge, we must account for both the addition and removal of connections.
Methods
We treat link prediction as a binary classification task for two separate events: Add and Remove. We evaluate eleven structural features derived from social network theory, grouping them into five models:
- Preferential Attachment: High-degree nodes attract more links.
- Embedding: Nodes with common neighbors are more likely to link.
- Reciprocity: Mutual linking patterns.
- Liability of Newness: Fragility of newer links vs. established ones.
- Instability: Frequent changes signal future gains or losses.
By analyzing predictive power for both additions and removals, we classify indicators into four roles: Growth (predicts additions; discourages removals), Decay (discourages additions; predicts removals), Stability (discourages both), and Instability (predicts both).
Datasets
Our study utilizes the directed article-hyperlink networks of four major Wikipedias: French, German, Italian, and Dutch. The French dataset was the largest, with approximately 1.8 million articles and over 41 million link additions. We analyzed every "add," "delete," and "update" event up to August 2011.
Key Results
Predicting a new link is significantly more accurate (AUC $\approx$ 0.90) than predicting a removal (AUC $\approx$ 0.75). This suggests that while growth follows clear structural rules, deletions are often driven by external factors like editorial disputes.
We successfully mapped traditional indicators to our four-class framework:
- Growth Indicators: Common Neighbors ($CN$) and Paths of Length Three ($P3$) are the strongest signals for network growth.
- Instability Indicators: High node degree ($d$) and the Node Deletion Coefficient ($ndc$) signal that a node is in a state of flux, gaining and losing links rapidly.
- Stability Indicators: A low deletion coefficient and "old" edges are the best predictors that a network structure will remain unchanged. The "Liability of Newness" finding confirms that the age of a link is a primary indicator of its survival; the longer a link survives, the less likely it is to be deleted.
Conclusion
This work demonstrates that structural indicators can effectively predict both the birth and death of knowledge links. Future work should combine these structural signals with semantic analysis to better understand the contextual reasons behind link removals and apply this framework to other dynamic knowledge domains.
Summary updated