Scalable algorithm for keyword aware influential community search in large social networks

Abstract

An influential community is defined as a closely connected group of people who have some dominance over the populace. In a social network, usually each individual has expertise in various topics. We consider the scenario where the network is represented as an attributed graph, users being the vertices, and their social connections being the edges. The attributes of each node is a set of keywords, representing the topics in which the corresponding user has some expertise. Additionally, for each user, keywords are paired with an expertise score representing how much expertise the user has in the representative topic. In such an attributed graph, we study the problem of finding the most influential communities given a combination of keywords as a query. A concern in keyword based community search is that, there can be millions of keywords in real life social networks. It is not user friendly to assume that users can raise queries using the keywords exactly as in the attributed graph. In this context, we propose a novel word-embedding based similarity model that enables semantic community search, which substantially alleviates the limitations of exact keyword based community search. Next, we propose a new influence measure for a community that considers both the cohesiveness of the community and the expertise scores of the members of the community in topics relevant to the query. Such a measure eliminates the need for specifying values of internal parameters of a network. Finally, we propose two efficient algorithms followed by a basic solution for searching influential communities in large attributed graphs. We present detailed experiments and a case study to demonstrate the effectiveness and efficiency of the proposed approaches.