Cooke, Richard J. E. (2006) Link prediction and link detection in sequences of large social networks using temporal and local metrics, MSc.
![[img]](http://pubs.cs.uct.ac.za/style/images/fileicons/application_pdf.png) |
PDF
Richard_Cooke_-_Link_prediction_and_link_detection_in_sequences_of_large_social_networks_using_temporal_and_local_metrics_(masters_dissertation)_-_2006.pdf Download (3MB) |
Abstract
This dissertation builds upon the ideas introduced by Liben-Nowell and Kleinberg in The Link Prediction Problem for Social Networks [42]. Link prediction is the problem of predicting between which unconnected nodes in a graph a link will form next, based on the current structure of the graph. The following research contributions are made: • Highlighting the difference between the link prediction and link detection problems, which have been implicitly regarded as identical in current research. Despite hidden links and forming links having very highly significant differing metric values, they could not be distinguished from each other by a machine learning system using traditional metrics in an initial experiment. However, they could be distinguished from each other in a "simple" network (one where traditional metrics can be used for prediction successfully) using a combination of new graph analysis approaches. • Defining temporal metric statistics by combining traditional statistical measures with measures commonly employed in financial analysis and traditional social network analysis. These metrics are calculated over time for a sequence of sociograms. It is shown that some of the temporal extensions of traditional metrics increase the accuracy of link prediction. • Defining traditional metrics using different radii to those at which they are normally calculated. It is shown that this approach can increase the individual prediction accuracy of certain metrics, marginally increase the accuracy of a group of metrics, and greatly increase metric computation speed without sacrificing information content by computing metrics using smaller radii. It also solves the “distance-three task” (that common neighbour metrics cannot predict links between nodes at a distance greater than three). • Showing that the combination of local and temporal approaches to link prediction can lead to very high prediction accuracies. Furthermore in “complex” networks (ones where traditional metrics cannot be used for prediction successfully) local and temporal metrics become even more useful.
| Item Type: | Electronic thesis or dissertation (MSc) |
|---|---|
| Uncontrolled Keywords: | social network analysis, social networks, link prediction, link detection, temporal networks, temporal analysis, graph theory, local networks |
| Subjects: | Computer systems organization > Architectures > Other architectures Applied computing > Law, social and behavioral sciences Mathematics of computing > Probability and statistics Social and professional topics Computer systems organization > Architectures > Distributed architectures |
| Date Deposited: | 04 Dec 2006 |
| Last Modified: | 10 Oct 2019 15:35 |
| URI: | http://pubs.cs.uct.ac.za/id/eprint/370 |
Actions (login required)
 |
View Item |