Dissertation
Link Prediction in Dynamic Networks
Doctor of Philosophy (PhD), Washington State University
01/2015
Handle:
https://hdl.handle.net/2376/6214
Abstract
Link Prediction in dynamic networks aims to model the patterns of relationship formation between any two agents in a multi-agent network for predicting the future links. We present three contributions to the state-of-the-art supervised link prediction (SLP) solutions, approaching the problem from three mutually exclusive, nonetheless, related perspectives in dynamic networks. First, we propose \\emph{Feature Evolution based LP} (FELP), which uses a two-step solution strategy. The initial step consists of constructing novel yet simple features using a combination of domain and topological attributes of the network. Next, we perform unconstrained node selection to identify potential candidates for prediction by any generic two-class learner. Our experiments on a real-world large collaboration network show the effectiveness of our framework over a sophisticated baseline. Second, we predict links between two connected components in a dynamic network, using intuitive network topological features, a novel feature processing technique especially when time is involved, and two different ways of learning a classifier based on the amount of historical data collected. Based on extensive experiments on two real-world collaboration networks, our \\emph{History based Eccentric LP} (HELP) method achieves up to 13\\% improvement over the baseline on edges with no historical data; on edges with historical data, we observed up to 3x improvement over the baseline. Since SLP is an extreme class-skew problem, we analyze the behavior of two leading performance measures for imbalanced learning, and prove the conditions for their dissonance. We also prove and validate the effect of relative increase in imbalance on the magnitude of a performance score. Third, to address the inherent class-skew, we propose \\emph{Minority Credit based LP} (MCLP) that uses one-class learning on only minority class examples. Moreover, our framework can extract additional data from the network evolution thereby dealing with the data scarcity. Our experimen
Metrics
3 File views/ downloads
15 Record Views
Details
- Title
- Link Prediction in Dynamic Networks
- Creators
- Jeyanthi Salem Narasimhan
- Contributors
- Lawrence B Holder (Advisor)Diane J Cook (Committee Member)Matthew E Taylor (Committee Member)
- Awarding Institution
- Washington State University
- Academic Unit
- Electrical Engineering and Computer Science, School of
- Theses and Dissertations
- Doctor of Philosophy (PhD), Washington State University
- Number of pages
- 164
- Identifiers
- 99900581638201842
- Language
- English
- Resource Type
- Dissertation