Exploring the Power of Frequent Neighborhood Patterns on Edge Weight Estimation

Since links on social networks model a mixture of many factors, such as acquaintances and friends, the problem of link strength prediction arises: given a social tie $e=(u,v)$ in a social network, how strong the tie $e$ is? Previous work tackles this problem mainly by node profile-based methods, i.e., utilizing users' profile information. However, some networks do not have node profiles. In this thesis, we study a novel problem of exploring the power of frequent neighborhood patterns on edge weight estimation. Given a labeled graph, we estimate its edge weights by applying its structural information as features. We develop an efficient pattern-growth based mining algorithm to mine frequent neighborhood patterns as features to estimate edge weights. Our experimental results on two real datasets show the efficiency of our method and the effectiveness of the frequent neighborhood pattern based features.