Mining Missing Links in Directed Social Networks based on Significant Motifs

Link prediction in directed social networks is a challenging and promising problem in both communication networks and data mining. Most existing methods of mining missing directed links are based on structural similarity and the inner contributions of neighborhood nodes are usually ignored. In this paper, taking node attributes into consideration, the potential value of each node is deduced based on a value transfer function. Combing the effects of two significant network motifs, a potential value index (PVI) for link prediction is proposed. PVI can utilize the in-depth information of surrounding environments. It also reflects the motivation of link formation in directed social networks. Experimental results on eight real-world social networks show that PVI outperforms eight state-of-the-art indices with only a quasi-local complexity. It can be well applied in large scale networks.

I. Introduction

Numerous of real-world systems can be described with complex networks, in which nodes represent individuals and links represent interactions [ 1 – 2 ]. Examples of complex networks include on-line social networks [3] , phone call networks, Internet networks, protein interaction networks [4] , and so on. For the last two decades, properties and dynamics of complex networks have been a high value topic. Understanding the inner essence of complex networks can help us get a better view of those complex systems, making it possible to control them [5] . However, constrained by technical insufficiency, it is almost impossible to get an intact view of a complex network. For example, in biological researches, nearly 80% of interactions between proteins in yeast still remain unobservable [4] , and merely 0.3% of human protein interaction network has been discovered [6] . To advance the progress of scientific researches, prediction methods are practical to reconstruct the incomplete network.