Anjan Chowdhury
ABSTRACT
Constant communities, i.e., groups of vertices that are always clustered together, independent of the community detection algorithm used, are necessary for reducing the inherent stochasticity of community detection results. Current methods for identifying constant communities require multiple runs of community detection algorithm(s). This process is extremely time consuming and not scalable to large networks. We propose a novel approach for finding the constant communities, by transforming the problem to a binary classification of edges. We apply the Otsu method from image thresholding to classify edges based on whether they are always within a community or not. Our algorithm does not require any explicit detection of communities and can thus scale to very large networks of the order of millions of vertices. Our results on real-world graphs show that our method is significantly faster and the constant communities produced have higher accuracy (as per F1 and NMI scores) than state-of-the-art baseline methods.
- T. Chakraborty, S. Srinivasan, N. Ganguly, S. Bhowmick, and A. Mukherjee, "Constant communities in complex networks," Scientific Reports, vol. 3, no. 1, 2013.Google Scholar
- N. Otsu, IEEE Transactions on Systems, Man and Cybernetics, no. 1.Google ScholarCross Ref
- D.-Y. Huang and C.-H. Wang, "Optimal multi-level thresholding using a two-stage otsu optimization approach," Pattern Recognition Letters, vol. 30, pp. 275--284, February 2009.Google ScholarDigital Library
- V. D. Blondel, J.-L. Guillaume, R. Lambiotte, and E. Lefebvre, "Fast unfolding of communities in large networks," J. of Stat. Mech., no. 10, p. P10008, 2008.Google ScholarCross Ref
- M. Rosvall and C. T. Bergstrom, "Maps of random walks on complex networks reveal community structure," PNAS, vol. 105, no. 4, pp. 1118--1123, 2008.Google ScholarCross Ref
- U. N. Raghavan, R. Albert, and S. Kumara, "Near linear time algorithm to detect community structures in large-scale networks," Phys. Rev. E, vol. 76, no. 3, Sep 2007.Google ScholarCross Ref
- S. P. Kolodziej, M. Aznaveh, M. Bullock, J. David, T. A. Davis, M. Henderson, Y. Hu, and R. Sandstrom, "The suitesparse matrix collection website interface," Journal of Open Source Software, vol. 4, no. 35, p. 1244, 2019.Google ScholarCross Ref
- R. Guimerà, L. Danon, A. Díaz-Guilera, F. Giralt, and A. Arenas, "Self-similar community structure in a network of human interactions," Phys. Rev. E, vol. 68, no. 6, Dec 2003.Google ScholarCross Ref
- T. Chakraborty, S. Srinivasan, N. Ganguly, A. Mukherjee, and S. Bhowmick, "On the permanence of vertices in network communities." in KDD. ACM, 2014, pp. 1396--1405.Google Scholar
- J. Leskovec and A. Krevl, "SNAP Datasets: Stanford large network dataset collection," http://snap.stanford.edu/data, Jun. 2014.Google Scholar
- A. Tandon, A. Albeshri, V. Thayananthan, W. Alhalabi, and S. Fortunato, "Fast consensus clustering in complex networks," Phys. Rev. E, no. 4, Apr 2019.Google ScholarCross Ref
- W. Weir, S. Emmons, R. Gibson, D. Taylor, and P. Mucha, "Post-processing partitions to identify domains of modularity optimization," Algorithms, vol. 10, no. 3.Google Scholar
- "A comprehensive literature review on community detection: Approaches and applications," Procedia Computer Science.Google Scholar
- M. A. Riolo and M. E. J. Newman, "Consistency of community structure in complex networks," Phys. Rev. E, vol. 101, no. 5, May 2020.Google ScholarCross Ref
- A. Lancichinetti and S. Fortunato, "Consensus clustering in complex networks," Sci. Rep., vol. 2, no. 1, Mar 2012.Google Scholar
- L. Jeub, O. Sporns, and S. Fortunato, "Multiresolution consensus clustering in networks," Scientific Reports, vol. 8, February 2018.Google Scholar
- V. Poulin and F. Théberge, "Ensemble clustering for graphs: comparisons and applications," Applied Network Science, vol. 4, no. 1, p. 51, 2019.Google ScholarCross Ref
- T. Chakraborty, N. Park, and V. S. Subrahmanian, "Ensemble-based algorithms to detect disjoint and overlapping communities in networks," pp. 73--80, Aug 2016.Google Scholar
- T. Chakraborty, "On the discovery of invariant groups in complex networks," Journal of Complex Networks, vol. 5, pp. 734--749, 10 2017.Google Scholar
- N. Nguyen, A. Alim, T. Dinh, and M. Thai, "A method to detect communities with stability in social network," Social Network Analysis and Mining, vol. 4, 08 2014.Google ScholarCross Ref
Index Terms
- Constant community identification in million scale networks using image thresholding algorithms
Recommendations
Magnet community identification on social networks
KDD '12: Proceedings of the 18th ACM SIGKDD international conference on Knowledge discovery and data miningSocial communities connect people of similar interests together and play essential roles in social network applications. Examples of such communities include people who like the same objects on Facebook, follow common subjects on Twitter, or join ...
Overlapping community detection at scale: a nonnegative matrix factorization approach
WSDM '13: Proceedings of the sixth ACM international conference on Web search and data miningNetwork communities represent basic structures for understanding the organization of real-world networks. A community (also referred to as a module or a cluster) is typically thought of as a group of nodes with more connections amongst its members than ...
Community detection in large-scale social networks
WebKDD/SNA-KDD '07: Proceedings of the 9th WebKDD and 1st SNA-KDD 2007 workshop on Web mining and social network analysisRecent years have seen that WWW is becoming a flourishing social media which enables individuals to easily share opinions, experiences and expertise at the push of a single button. With the pervasive usage of instant messaging systems and the ...
Comments