Community detection is expensive, and the cost generally depends at least linearly on the number of vertices in the graph. We propose working with a reduced graph that has many fewer nodes but nonetheless captures key community structure. The K-core of a graph is the largest subgraph within which each node has at least K connections. We propose a framework that accelerates community detection by applying an expensive algorithm (modularity optimization, the Louvain method, spectral clustering, etc.) to the K-core and then using an inexpensive heuristic (such as local modularity maximization) to infer community labels for the remaining nodes. Our experiments demonstrate that the proposed framework can reduce the running time by more than 80 while preserving the quality of the solutions. Recent theoretical investigations provide support for using the K-core as a reduced representation.
Some papers discuss the existence condition of a @math -core subgraph @cite_12 @cite_5 . Some study the relationship between the @math -core and the percolation dynamics @cite_0 , and it is worth noting that the bond percolation is quite similar to the label propagation in community detection @cite_35 . Recently, @math -core is also used to evaluate the robustness of communities, which reflects the collaborative nature in co-authorship graphs @cite_11 .
@cite_35 @cite_0 @cite_5 @cite_12 @cite_11
2325532214 2005443809 1508206940 2275369912
Consider a one-dimensional independent bond percolation model withpj denoting the probability of an occupied bond between integer sitesi andi±j,j≧1. Ifpj is fixed forj≧2 and ( j )j2pj>1, then (unoriented) percolation occurs forp1 sufficiently close to 1. This result, analogous to the existence of spontaneous magnetization in long range one-dimensional Ising models, is proved by an inductive series of bounds based on a renormalization group approach using blocks of variable size. Oriented percolation is shown to occur forp1 close to 1 if ( j )jspj>0 for somes<2. Analogous results are valid for one-dimensional site-bond percolation models. Percolation with edge-passage probability p and first-passage percolation are studied for the n-cube Bn = 0, 1 with nearest neighbor edges. For oriented and unoriented percolation, p = e n and p = 1 n are the respective critical probabilities. For oriented first-passage percolation with i.i.d. edge-passage times having a density of 1 near the origin, the percolation time (time to reach the opposite corner of the cube) converges in probability to 1 as n → ∞. This resolves a conjecture of David Aldous. When the edge-passage distribution is standard exponential, the (smaller) percolation time for unoriented edges is at least 0.88. These results are applied to Richardson’s model on the (unoriented) n-cube. Richardson’s model, otherwise known as the contact process with no recoveries, models the spread of infection as a Poisson process on each edge connecting an infected node to an uninfected one. It is shown that the time to cover the entire n-cube is bounded between 1.41 and 14.05 in probability as n→∞. Research supported by the National Security Agency under Grant Number MDA904-89-H-2051. Research supported by a National Science Foundation postdoctoral fellowship and by a Mathematical Sciences Institute postdoctoral fellowship. AMS 1991 subject classifications. Primary 60K35; secondary 60C05. We study the number @math of open paths of length @math in supercritical oriented percolation on @math , with @math . We prove that on the percolation event @math , @math almost surely converges to a positive deterministic constant. We also study the existence of directional limits. The proof relies on the introduction of adapted sequences of regenerating times, on subadditive arguments and on the properties of the coupled zone in supercritical oriented percolation. Theoretical attempts proposed so far to describe ordinary percolation processes on real-world networks rely on the locally treelike ansatz. Such an approximation, however, holds only to a limited extent, because real graphs are often characterized by high frequencies of short loops. We present here a theoretical framework able to overcome such a limitation for the case of site percolation. Our method is based on a message passing algorithm that discounts redundant paths along triangles in the graph. We systematically test the approach on 98 real-world graphs and on synthetic networks. We find excellent accuracy in the prediction of the whole percolation diagram, with significant improvement with respect to the prediction obtained under the locally treelike approximation. Residual discrepancies between theory and simulations do not depend on clustering and can be attributed to the presence of loops longer than three edges. We present also a method to account for clustering in bond percolation, but the improvement with respect to the method based on the treelike approximation is much less apparent.