Mining hidden links in social networks to achieve equilibrium

作者：Ma, Huan; Lu, Zaixin; Li, Deying^*; Zhu, Yuqing; Fan, Lidan; Wu, Weili

来源：Theoretical Computer Science, 2014, 556: 13-24.

DOI：10.1016/j.tcs.2014.08.006

• Mining hidden links
• Vertex pair proximity
• Approximation algorithm
• Nash equilibrium
• Social networks

Although more connections between individuals in a social network can be identified with the development of high techniques, to obtain the complete relation information between individuals is still hard due to complex structure and individual privacy. However, the social networks have communities. In our work, we aim at mining the invisible or missing relations between individuals within a community in social networks. We propose our algorithm according to the fact that the individuals exist in communities satisfying Nash equilibrium, which is borrowed from game-theoretic concepts often used in economic researches. Each hidden relation is explored through the individual's loyalty to their community. To the best of our knowledge, this is the first work that studies the problem of mining hidden links from the aspect of Nash equilibrium. Eventually we confirm our approach's superiority from extensive experiments over real-world social networks.

• 出版日期2014-10-30
• 单位中国人民大学