Literature Survey on Finding Influential Communities in Large Scale Networks <s> III. PROBLEM STATEMENT <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> III. PROBLEM STATEMENT <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> III. PROBLEM STATEMENT <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 to capture the influence of a community. Based on this 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 data structure which supports efficient search of the top-r k-influential communities in optimal time. We also propose an efficient algorithm to maintain the data structure when the network is frequently updated. Additionally, we propose a novel I/O-efficient algorithm to find the top-r k-influential communities in a disk-resident graph under the assumption of \({{\mathcal {U}}}=O(n)\), where \({{\mathcal {U}}}\) and n denote the size of the main memory and the number of nodes, respectively. Finally, we conduct extensive experiments on six real-world massive networks, and the results demonstrate the efficiency and effectiveness of the proposed methods. <s> BIB003 </s> Literature Survey on Finding Influential Communities in Large Scale Networks <s> III. PROBLEM STATEMENT <s> Detecting social communities in large social networks provides an effective way to analyze the social media users' behaviors and activities. It has drawn extensive attention from both academia and industry. One essential aspect of communities in social networks is outer influence which is the capability to spread internal information of communities to external users. Detecting the communities of high outer influence has particular interest in a wide range of applications, e.g., Ads trending analytics, social opinion mining and news propagation pattern discovery. However, the existing detection techniques largely ignore the outer influence of the communities. To fill the gap, this work investigates the Most Influential Community Search problem to disclose the communities with the highest outer influences. We firstly propose a new community model, maximal kr-Clique community, which has desirable properties, i.e., society, cohesiveness, connectivity, and maximum. Then, we design a novel tree-based index structure, denoted as C-Tree, to maintain the offline computed r-cliques. To efficiently search the most influential communities, we also develop four advanced index-based algorithms which improve the search performance of non-indexed solution by about 200 times. The efficiency and effectiveness of our solution have been extensively verified using six real datasets and a small case study. <s> BIB004 </s> Literature Survey on Finding Influential Communities in Large Scale Networks <s> III. PROBLEM STATEMENT <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> BIB005
Consider a Graph G(V, E) where V is the set of vertices and E is the set of edges. Let d(v, G) be defined as the degree of vertex v in graph G i.e number of edges coming out of v. A kcore is an induced subgraph where the degree of each node is atleast k ( d(v, H) ≥ k). A maximal k-core is a k-core which is not a subset of any other k-core. Clearly, every graph will have a unique maximal k-core for every values of 'k'. To introduce the concept of influence we assign a weight to each node which can be interpreted as its influence (such as PageRank, h-index etc). A weight vector of a Graph is the set of all weights assigned to the nodes. Given a graph G(V, E) and an induced graph H(V h , E h ), we define a function to compute the influence of this induced subgraph. One possible definition, as discussed earlier, could be taking the minimum weight present in the induced subgraph. The intuition behind it is that an induced subgraph is as influential as its least influential member BIB001 . Another way could be taking the average of all the weights present in the subgraph or even a more complex function can be defined. A k-influential community BIB001 is an induced subgraph Each node has degree atleast k 3) Is maximal Problem : Given a graph G = (V, E), a weight vector W, and two parameters k and r, the problem is to find the top-r k-influential communities with the highest influence value. BIB001 IV. ALGORITHMS USED The problem statement for finding the most influential communities was first formulated by Li et al BIB001 . They developed a formal definition of influence of an individual and a community, and suggested various methods and optimization to solve the problem. The idea behind their algorithm is to start with the maximal k-core of the graph and then remove nodes from it one at a time, following a certain rule, which will give us the communities present in the graph in an increasing order of influence. The details of the algorithm are discussed below. k-core : The first step is to calculate the maximal k-core of the graph. This will contain disjoint sets of connected components, each of them satisfying the definition of a community. We then remove a node, present in the k-core, which has the least influence and store its parent community. The maximal k-core of this new graph (formed after removing the node as mentioned above) is calculated and the whole process is repeated again, until we find no maximal k-core. The authors defined the influence of a community equal to the least influential node present in the community. Due to the use of this definition, the influence value of the community stored at any iteration will be the least among all the communities present in the k-core at that iteration, since it contains the node with the least influence. This ensures that the influence value of communities stored at every iteration keeps on increasing. The final output of the algorithm, i.e. the top-r k-influential communities, are the communities stored in the last r iterations. Calculating k-core for every iteration was identified by the authors as the costliest part of the algorithm. In a graph with m edges, the time taken by the algorithm to perform n k iterations is O(n k m) BIB001 . It is easy to notice that the only change between the maximal k-core of two consecutive iterations occurs in the community from which the least influential node was removed. Thus, as suggested by Li et al BIB001 , we can easily avoid recalculating the k-core at every iteration by using the k-core of the previous iteration, and removing certain nodes from it which are not a part of the k-core anymore. These nodes can be easily identified by performing DFS from the removed node BIB001 . The optimization proposed above reduces the time complexity of our algorithm to O(m + n), where m and n represent the edges and vertices present in the graph respectively. ICPS : The method of using DFS is sufficiently fast when dealing with only a single query of finding the top-r kinfluential communities. However, repeating the same process for different values of k becomes infeasible for large graphs. A naive approach to overcome this could be to store the topr k-influential communities for every value of k upto some k max . The time complexity now will be O(k max (m + n)) for any number of queries. An obvious limitation to this method is the amount of space required to store the answers for every value of k. To counter this limitation, Li et al BIB003 introduced a novel data structure, called influential community-preserved structure (ICPS). This structure compresses and stores the top-r kinfluential communities for all values of k upto k max in space complexity O(m). Once this data structure is created, it takes time O(n a ), where n a represents the number of vertices in the answer, to extract the answer for any query. Li et al BIB003 also suggested an optimization to this precomputation, reducing the time complexity to O(pm), where p is the arboricity of the graph, m total number of edges. The arboricity of an undirected graph is the minimum number of forests into which its edges can be partitioned. Forward / Backward Algorithm : Chen et al BIB002 provided two important extensions to the above algorithm, namely forward and backward algorithms. They identified the computation of Maximal Connected Component (MCC) as the slow step of the algorithm. MCC computation is done at the end of each iteration, to find the parent community of the deleted node. The forward algorithm, maintain a hash table to keep track of the deleted nodes and then computes the MCCs later in the reverse order, thereby ensuring that only the top-r most influential communities are computed. The backward algorithm, start with the most influential node present in the graph and then adds nodes in decreasing order of influence. After every addition, the algorithm checks whether the k-core property is satisfied, thus finding the top-r k-influential communities from most influential to least. The process is rather slow as compared to forward algorithm, however outperforms it for very small values of r. Thus, for smaller values of r, backward algorithm should be used, and switch to forward algorithm when the value of r increases. Chen et al BIB002 also used WebGraph  , a graph compression framework to reduce the space complexity of the compressed graph storage. LocalSearch : Bi et al BIB005 introduced LocalSearch, a novel algorithm that works by reducing the community search problem to a local area in a subgraph containing only the nodes with influence greater than a threshold. The threshold influence is chosen such that it is the minimum influence at which there are atleast r k-influential communities in the subgraph. Any kinfluential community not found in this subgraph, but actually present in the original graph, will have influence less than any community found in this subgraph (since it will contain atleast one node with influence less than the threshold). This way, the top-r k-influential communities found in this subgraph will be the top-r k-influential communities of the complete graph. The algorithm proposed starts with a heuristically chosen threshold and then expands the graph until there are at least r k-influential communities in the sub graph. To speed up the calculation of the number of k-influential communities in a subgraph, the authors define a new term, keynode, which is simply the least influential node of a k-community. The advantage of finding just the keynodes is that we do not need to calculate the MCCs of the graph. While removing least influential nodes from the k-core, as done in the forward algorithm by Chen et al BIB002 , the algorithm also maintains an array of all the nodes deleted during DFS at each iteration. After all the iterations, instead of calculating MCCs for the top r keynodes, it introduces a different recursive method of identifying the communities. We start with all the nodes deleted at the (T − p) th iteration, where T is the total number of iterations. These are extended to include all the nodes in the (p + 1) th k-influential community which are connected to them, thus resulting in the p th k-influential community. The first k-influential community is simply all the nodes deleted in the last iteration. The proof of correctness can be found in BIB005 . kr-clique : We have been discussing till now the optimizations for the algorithm defined by Li et al BIB001 . However, the definition by Li et al BIB001 is not universally accepted. Wang et al BIB004 recently introduced a new definition of influence, and focused on the idea of using kr-clique rather than the traditional k-core for finding top-r k-influential communities. We will not be discussing the definition used by them, however will discuss the algorithms they used, since their proposed solutions can be easily translated to our problem statement. A kr-clique is defined such that every node has k edges and every nodes is reachable in atmost r hops from any node. This ensures more cohesiveness in the community than a k-core, since in a k-core two nodes can be very far from each other, which is not true in a kr-clique. Wang et al BIB004 first provides a baseline algorithm for their influence model. The algorithm iterates through all the nodes in the graph, computing maximal kr-clique for that node and then calculating its influence. This is clearly a brute force algorithm, not suitable for large graphs. To improve the performance of the algorithm, the authors introduce a novel data structure, namely C-tree, which indexes maximal r-cliques generated by the graph. C-trees are space and time efficient when it comes to generating kr-cliques. The authors list four methods of searching through the C-tree, sequentialorder based (SO) search, improved sequential-order based (SO+) search, best-first based (BF) search, and fast best first based (BF+) search. Progressive Approach : All the algorithms discussed above outputs the final answer, i.e all the top-r k-influential communities, in one go. This leads to a significant latency between the query and the result. To handle this Bi et al BIB005 suggests a progressive approach in which the communities are generated in decreasing order one after the other. In the first iteration, the problem statement is finding the top-1 k-influential community. The threshold and subgraph is selected, as mentioned in LocalSearch, and the top-1 k-influential community is provided as the output. Now, the threshold is shifted, so as to Fig. 1 . Statistics of real graph. Image courtesy Bi et al BIB005 double the size of the subgraph. The LocalSearch now outputs another set of k-communities. This process is repeated until the require number of k-communities are provided. V. DATASETS Bi et al BIB005 provides an extensive comparison between the algorithms discussed in this survey BIB001 , BIB003 , BIB005 , BIB002 by doing experiments across a variety of datasets. All the experimentation results presented here were taken from Bi et al BIB005 . The algorithms compared are, 1) OnlineAll :-DFS and ICPS based algorithm by Li et al BIB001 , BIB003 . Bi et al BIB005 . But using OnlineAll, instead of keynodes. (For comparison purpose) 6) LocalSearch-P :-Local Algorithm algorithm with the progressive approach integrated as shown by Bi et al BIB005 . All algorithms were implemented in C++ and compiled in GNU GCC 4.8.2 with the -O3 flag. The experiments were conducted on Intel i5 3.20GHz CPU and 16GB main memory BIB005 . Graphs : The dataset contains eight real graphs, Email, Youtube, Wiki, LiveJ, Orkut, Arabic, UK and Twitter. The first five are from the Stanford Network Analysis Platform [12] , and the last three are from the Laboratory of Web Algorithmics [13] . The variability across different graphs can be found in Fig 1. The two parameters r and k were varied as follows, r chosen from {5, 10, 20, 50, 100} and k chosen from {5, 10, 20, 50}. For every query the algorithms were run three times and the average CPU time in milliseconds was reported. Comparison between LocalSearch and LocalSearch-P for r=128, k=10 and 50. Courtesy Bi et al BIB005 VI. COMPARATIVE ANALYSIS The OnlineAll and Forward algorithms work on the whole graph for any value of k and r and hence there is very little change in the total time taken for processing queries when the values of k or r are varied. The forward algorithm performs slightly better than the OnlineAll algorithm because of the reduced number of Maximal Connected Component(MCC) computations. (refer to Fig 2,3,4) The Backward algorithm starts from the most influential community and stops when the top-r most influential communities have been found. Hence the time taken by Backward algorithm increases with the increase in the value of r (refer to Fig 5) . The total time for LocalSearch algorithm increases as we increase r keeping k constant. This can be easily explained, since at a higher value of r, the subgraph formed will be larger in size and hence the time taken will be more. Similar reasoning can be given for varying k and keeping r constant. The increase in the value of k means a larger sub graph is required to satisfy the stronger cohesive property and hence an increase in total time can be seen (refer to Fig 8) . LocalSearch-P outperforms every algorithm that we have discussed in this paper, including the variations LocalSearch and LocalSearch-OA (refer to Fig 2,3,4,5,6,8) . A comparison was done for the time taken to output top-p k-influential communities, p varying for 0 to r. Since LocalSearch gives the complete output in one go, the time for every value of p is the same. However, the progressive approach delivers the initial results almost immediately and then the time taken gradually increases (refer to Fig 8) .