Literature Survey on Finding Influential Communities in Large Scale Networks <s> A. Non-containment Community Search <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> A. Non-containment Community Search <s> Finding decompositions of a graph into a family of communities is crucial to understanding its underlying structure. Algorithms for finding communities in networks often rely only on structural information and search for cohesive subsets of nodes. In practice however, we would like to find communities that are not only cohesive, but also influential or important. In order to capture such communities, Li, Qin, Yu, and Mao introduced a novel community model called "k-influential community" based on the concept of $k$-core, with numerical values representing "influence" assigned to the nodes. They formulate the problem of finding the top-r most important communities as finding r connected k-core subgraphs ordered by the lower-bound of their importance. In this paper, our goal is to scale-up the computation of top-r, k-core communities to web-scale graphs of tens of billions of edges. We feature several fast new algorithms for this problem. With our implementations, we show that we can efficiently handle massive networks using a single consumer-level machine within a reasonable amount of time. <s> BIB002 </s> Literature Survey on Finding Influential Communities in Large Scale Networks <s> A. Non-containment Community Search <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> BIB003
Following the definition of k-communities, it is possible that an influential k-community is a subgraph of another influential k-community. However, for most of the practical applications, one would prefer to not have such relations present in the output. Thus the problem statement of finding top-r noncontainment influential k-communities was introduced. OnlineAll BIB001 checks for every community generated whether it contains a k-core or not and only those are considered for the final output which have no k-cores present in it. Forward Algorithm BIB002 uses an additional array to store the degree of a node and then used its value to check for non-containment. A slight modification in LocalSearch BIB003 was also suggested in the algorithm to tackle the above task. To summarize we can say that the modified problem statement can be easily solved by providing slight modifications to the existing algorithms.