Contact Student: Jeyanthi Salem Narasimhan, jsalemna@eecs.wsu.edu

Details:

In simple terms, link prediction problem is about finding whether an edge or link might appear between two nodes of a network or in other words, it amounts to asking when two nodes of a network would communicate. The network under consideration could be a static one or dynamic. When the underlying graph is static, traditionally the problem is addressed with only the topology of the graph into account. In my work, I predominantly work with dynamic graphs, where a number of factors, both exogenous and endogenous to the network, contribute towards formation of links. Conventional way of addressing this problem takes snapshots of graphs over a period of time and tries to predict links in a future time. Out of many ways of analyzing this problem, my trials are inspired from concepts in Mathematical Sociology where the importance of macro-micro linkage is well studied and established. Since I am looking at evolution of networks in general, a domain independent modeling is the one to tackle this problem.

Currently, I am trying to model network evolution with stochastic processes with their dynamics studied using master equation and its variants. What makes such concepts interesting and important is that such concepts have been used to study evolving networks from diverse domains like chemistry (study of chemical reactions), biological networks (evolution of cells, molecular biology), economics (study of social consumption, group sentiments etc), statistical physics and many other physical systems. I think that link prediction among two nodes is a micro portion of the macro evolution of networks and hence if the modeling of network is successful, the link prediction becomes tractable. I aim to build a unified modeling framework which can be applied to study of network evolution from any domain with a little domain related knowledge. Modeling of network evolution is a hard problem because of the parameters involved in the stochastic dynamics and non-availability of closed-form solutions to the equations of interest.

Domains to which the problem is relevant: Link prediction has wide range of applicability. In addition to the physical systems mentioned in the second paragraph of the problem description, it can be used in the study of Internet and abstract networks like WWW, On-line Social Networks, Collaboration networks to mention few.

With the proliferation of social networking sites and some of them competing for the top position populationwise, it is worth noting that one of the key reasons for such success is the usage of link prediction for friends recommendation. 

Datasets (Not all are dynamic):

- SNAP (Stanford Network Analysis Platform)

- KDD cup Datasets - https://www.cs.cornell.edu/projects/kddcup/datasets.html

- On-line Social Network @ Maxplanck - https://socialnetworks.mpi-sws.org/data-imc2007.html

- MEJ Newman - https://www-personal.umich.edu/~mejn/netdata/

- A-L Barabasi - https://www.nd.edu/~networks/resources.htm

        https://www.barabasilab.com/rs-netdb.php

- Jon Kleinberg - https://www.cs.cornell.edu/Courses/cs685/2007fa/ (Scroll down for datasets)

- Pajek - https://vlado.fmf.uni-lj.si/pub/networks/data/

- A collection :https://math.nist.gov/~RPozo/complex_datasets.html

Relevant Publications:

- Link Prediction problem for social networks, Liben-Nowell et al, https://portal.acm.org/citation.cfm?id=1241551

- Evolution of the social network of Scientific collaborations, Barabasi et.al, https://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.115.8316

- Hierarchical Structure and the prediction of missing links in networks, Clauset et al, www-personal.umich.edu/~mejn/papers/cmn08.pdf

- Learning spectral graph transformations for link prediction, Kunegis et al, https://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.149.6681

- Link Prediction in relational data, Taskar et al, https://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.9.3546

- Temporality in Link Prediction: Understanding Social Complexity, Potgieter et al, https://emergentpublications.com/eco/ECO_papers/Issue_11_1_7_AC.pdf

- Cold start link  prediction, Leroy et al, https://users.cis.fiu.edu/~lzhen001/KDD_USB_key_2010/docs/p393.pdf