Internship at Stanford: Missing Link Prediction with Network Motifs

Summer 2011

Research internship at Stanford with Prof. Jure Leskovec. Worked on discovery of network motifs (statistically significant sub-graphs), and used the motifs with SVM to predict the missing links in information networks.

Network motifs are sub-graphs that repeat themselves in a specific network or among various networks. Each of these sub-graphs (a particular pattern of interactions between nodes) may reflect a functional property of the network. Network motifs may be a useful concept to uncover structural design principles of complex networks. However, their detection is computationally challenging.

In my internship, I worked on predicting the missing links in evolving networks, and investigate how the motifs (structures) evolve over time. I implemented efficient algorithms and data structures for sub-graph enumeration and counting, and used these methods to compute network motifs on various information networks. The obtained network motifs were features to SVM to predict the missing links in the networks.

Code (GitHub) (advanced SNAP components folder)

Other resources: Network motifs: theory and experimental approaches (Uri Alon, 2007)