Anita Zakrzewska
David A. Bader
ABSTRACT
A variety of massive datasets, such as social networks and biological data, are represented as graphs that reveal underlying connections, trends, and anomalies. Community detection is the task of discovering dense groups of vertices in a graph. Its one specific form is seed set expansion, which finds the best local community for a given set of seed vertices. Greedy, agglomerative algorithms, which are commonly used in seed set expansion, have been previously designed only for a static, unchanging graph. However, in many applications, new data is constantly produced, and vertices and edges are inserted and removed from a graph. We present an algorithm for dynamic seed set expansion, which incrementally updates the community as the underlying graph changes. We show that our dynamic algorithm outputs high quality communities that are similar to those found when using a standard static algorithm. The dynamic approach also improves performance compared to recomputation, achieving speedups of up to 600x.
- S. Fortunato, "Community detection in graphs," Physics Reports, vol. 486, no. 3, pp. 75--174, 2010.Google Scholar
Cross Ref
- J. Xie, S. Kelley, and B. K. Szymanski, "Overlapping community detection in networks: The state-of-the-art and comparative study," ACM Computing Surveys (CSUR), vol. 45, no. 4, p. 43, 2013. Google ScholarDigital Library
- M. E. Newman and M. Girvan, "Finding and evaluating community structure in networks," Physical review E, vol. 69, no. 2, p. 026113, 2004.Google ScholarCross Ref
- F. R. Chung, Spectral graph theory. American Mathematical Soc., 1997, vol. 92.Google Scholar
- F. Havemann, M. Heinz, A. Struck, and J. Gläser, "Identification of overlapping communities and their hierarchy by locally calculating community-changing resolution levels," Journal of Statistical Mechanics: Theory and Experiment, vol. 2011, no. 01, p. P01023, 2011.Google ScholarCross Ref
- R. Andersen, F. Chung, and K. Lang, "Local graph partitioning using pagerank vectors," in Foundations of Computer Science, 2006. FOCS'06. 47th Annual IEEE Symposium on. IEEE, 2006, pp. 475--486. Google ScholarDigital Library
- R. Andersen and K. J. Lang, "Communities from seed sets," in Proceedings of the 15th international conference on World Wide Web. ACM, 2006, pp. 223--232. Google ScholarDigital Library
- A. Clauset, "Finding local community structure in networks," Physical review E, vol. 72, no. 2, p. 026132, 2005.Google ScholarCross Ref
- J. Riedy, D. A. Bader, K. Jiang, P. Pande, and R. Sharma, "Detecting communities from given seeds in social networks," 2011.Google Scholar
- A. Lancichinetti, S. Fortunato, and J. Kertész, "Detecting the overlapping and hierarchical community structure in complex networks," New Journal of Physics, vol. 11, no. 3, p. 033015, 2009.Google ScholarCross Ref
- C. Lee, F. Reid, A. McDaid, and N. Hurley, "Detecting highly overlapping community structure by greedy clique expansion," in 4th SNA-KDD Workshop, 2010, p. 3342.Google Scholar
- V. Gómez, A. Kaltenbrunner, and V. López, "Statistical analysis of the social network and discussion threads in slashdot," in Proceedings of the 17th international conference on World Wide Web. ACM, 2008, pp. 645--654. Google ScholarDigital Library
- "Slashdot threads network dataset -- KONECT," Aug. 2014. {Online}. Available: http://konect.uni-koblenz.de/networks/slashdot-threadsGoogle Scholar
- M. D. Choudhury, H. Sundaram, A. John, and D. D. Seligmann, "Social synchrony: Predicting mimicry of user actions in online social media," in Proc. Int. Conf. on Computational Science and Engineering, 2009, pp. 151--158. Google ScholarDigital Library
- J. Yang and J. Leskovec, "Defining and evaluating network communities based on ground-truth," in Proc. ACM SIGKDD Workshop on Mining Data Semantics. ACM, 2012, p. 3. Google ScholarDigital Library
- A Dynamic Algorithm for Local Community Detection in Graphs
Recommendations
Dynamic chromatic number of regular graphs
A k-dynamic coloring of a graph G is a proper coloring of G with k colors such that for every vertex v@?V(G) of degree at least 2, the neighbors of v receive at least 2 colors. The dynamic chromatic number of a graph G, @g"2(G), is the least number k ...
Local coloring of Kneser graphs
A local coloring of a graph G is a function c:V(G)->N having the property that for each set S@__ __V(G) with 2@__ __|S|@__ __3, there exist vertices u,v@__ __S such that |c(u)-c(v)|>=m"S, where m"S is the number of edges of the induced subgraph . The ...
Local Clique Covering of Claw-Free Graphs
A k-clique covering of a simple graph G is a collection of cliques of G covering all the edges of G such that each vertex is contained in at most k cliques. The smallest k for which G admits a k-clique covering is called the local clique cover number of ...
Comments