Literature Survey on Finding Influential Communities in Large Scale Networks <s> II. MOTIVATION <s> Community search is a problem of finding densely connected subgraphs that satisfy the query conditions in a network, which has attracted much attention in recent years. However, all the previous studies on community search do not consider the influence of a community. In this paper, we introduce a novel community model called k-influential community based on the concept of k-core, which can capture the influence of a community. Based on the new community model, we propose a linear-time online search algorithm to find the top-r k-influential communities in a network. To further speed up the influential community search algorithm, we devise a linear-space index structure which supports efficient search of the top-r k-influential communities in optimal time. We also propose an efficient algorithm to maintain the index when the network is frequently updated. We conduct extensive experiments on 7 real-world large networks, and the results demonstrate the efficiency and effectiveness of the proposed methods. <s> BIB001 </s> Literature Survey on Finding Influential Communities in Large Scale Networks <s> II. MOTIVATION <s> Community search over large graphs is a fundamental problem in graph analysis. Recent studies propose to compute top-k influential communities, where each reported community not only is a cohesive subgraph but also has a high influence value. The existing approaches to the problem of top-k influential community search can be categorized as index-based algorithms and online search algorithms without indexes. The index-based algorithms, although being very efficient in conducting community searches, need to pre-compute a special-purpose index and only work for one built-in vertex weight vector. In this paper, we investigate on-line search approaches and propose an instance-optimal algorithm LocalSearch whose time complexity is linearly proportional to the size of the smallest subgraph that a correct algorithm needs to access without indexes. In addition, we also propose techniques to make LocalSearch progressively compute and report the communities in decreasing influence value order such that k does not need to be specified. Moreover, we extend our framework to the general case of top-k influential community search regarding other cohesiveness measures. Extensive empirical studies on real graphs demonstrate that our algorithms outperform the existing online search algorithms by several orders of magnitude. <s> BIB002
The problem of community search over very large graphs is a fundamental problem is graph analysis. However certain applications require us to find the 'r' most influential communities in the graph. Consider the following examples as described in Bi et al. BIB002 . Assume that Alice is a database researcher. She may want to identify the most influential research groups from the co-authorship network of the database community, so as to be aware of the recent trends of database research from those influential groups. Another frequently encountered example is in online social network domain. Suppose that Bob is an online social network user. He may want to follow the most influential groups in the social network, so as to track the recent activities from those influential groups. Both of these issues are common in the sense that they need to find communities in a graph with an additional property of having high influence. A possible definition of influence value can be defining it as the minimum weight of the nodes in that community BIB001 . An influential community is the one which has a large influence value, which in this case would mean every member of the community is highly influential (since we are taking the minimum). There has been a sudden outburst of different techniques in this field in the last few years, both in terms of new heuristics in the detection of most influential communities and in terms of speeding up the search algorithms. We aim to provide a thorough survey of the current progress as an entry point for future researchers and insights on possible future research directions.