1. Home
  2. Issues
  3. Volume 2, Issue 3 (2024)
  4. Constrained Community Detection in Socia ...

The New England Journal of Statistics in Data Science


Constrained Community Detection in Social Networks
Volume 2, Issue 3 (2024), pp. 368–379
Pub. online: 28 April 2023      Type: Methodology Article      Open accessOpen Access
Area: Statistical Methodology
Accepted
5 March 2023
Published
28 April 2023

Abstract

Community detection in networks is the process by which unusually well-connected sub-networks are identified–a central component of many applied network analyses. The paradigm of modularity quality function optimization stipulates a partition of the network’s vertexes that maximizes the difference between the fraction of edges within communities and the corresponding expected fraction if edges were randomly allocated among all vertex pairs while conserving the degree distribution. The modularity quality function incorporates exclusively the network’s topology and has been extensively studied whereas the integration of constraints or external information on community composition has largely remained unexplored. We define a greedy, recursive-backtracking search procedure to identify the constitution of high-quality network communities that satisfy the global constraint that each community be comprised of at least one vertex among a set of so-called special vertexes and apply our methodology to identifying health care communities (HCCs) within a network of hospitals such that each HCC consists of at least one hospital wherein at least a minimum number of cardiac defibrillator surgeries were performed. This restriction permits meaningful comparisons in cardiac care among the resulting health care communities by standardizing the distribution of cardiac care across the hospital network.

References

[1] 
Abramowitz, M. and Stegun, I. A. (1964) Handbook of Mathematical Functions with Formulas, Graphs, and Mathematical Tables. Dover. MR0415956
[2] 
Andrade, R. F. S., Rocha-Neto, I. C., Santos, L. B. L., de Santana, C. N., Diniz, M. V. C., Lobão, T. P., Góes-Neto, A., Pinho, S. T. R. and El-Hani, C. N. (2011). Detecting Network Communities: An Application to Phylogenetic Analysis. PLoS Computational Biology 7. https://doi.org/10.1371/journal.pcbi.1001131. MR2821650
[3] 
Barabási, A. L. and Pósfai, M. (2016) Network science. Cambridge University Press, Cambridge.
[4] 
Blondel, V. D., Guillaume, J.-L., Lambiotte, R. and Lefebvre, E. (2008). Fast unfolding of communities in large networks. Journal of Statistical Mechanics: Theory and Experiment 2008(10) 10008.
[5] 
Chung, F. R. K. (1997) Spectral Graph Theory. American Mathematical Society. MR1421568
[6] 
Csardi, G. and Nepusz, T. (2006). The igraph software package for complex network research. InterJournal Complex Systems 1695.
[7] 
Eaton, E. and Mansbach, R. (2021). A Spin-Glass Model for Semi-Supervised Community Detection. Proceedings of the AAAI Conference on Artificial Intelligence 26 900–906.
[8] 
Estrada, E. (2011) The Structure of Complex Networks: Theory and Applications. Oxford University Press, Inc., USA.
[9] 
Estrada, E. and Knight, P. A. (2015) A First Course in Network Theory. Oxford University Press, United Kingdom.
[10] 
Fortunato, S. (2010). Community detection in graphs. Physics Reports 486(3-5) 75–174. https://doi.org/10.1016/j.physrep.2009.11.002. MR2580414
[11] 
Gauzens, B., Thébault, E., Lacroix, G. and Legendre, S. (2015). Trophic groups and modules: two levels of group detection in food webs. Journal of the Royal Society Interface 12(106) 20141176.
[12] 
Girvan, M. and Newman, M. E. J. (2002). Community structure in social and biological networks. Proceedings of the National Academy of Sciences 99(12) 7821–7826. https://doi.org/10.1073/pnas.122653799. MR1908073
[13] 
Hendrickson, B. and Kolda, T. G. (2000). Graph Partitioning Models for Parallel Computing. Parallel Computing 26(12) 1519–1534. https://doi.org/10.1016/S0167-8191(00)00048-X. MR1786938
[14] 
Hu, Y., Wang, F. and Xierali, I. M. (2018). Automated Delineation of Hospital Service Areas and Hospital Referral Regions by Modularity Optimization. Health Services Research 53(1) 236–255.
[15] 
Hu, Y., Wang, F. and Xierali, I. M. (2018). Automated Delineation of Hospital Service Areas and Hospital Referral Regions by Modularity Optimization. Health services research 53 236–255.
[16] 
Javed, M. A., Younis, M. S., Latif, S., Qadir, J. and Baig, A. (2018). Community detection in networks: A multidisciplinary review. Journal of Network and Computer Applications 108 87–111.
[17] 
Jia, P., Wang, F. and Xierali, I. M. (2020). Evaluating the effectiveness of the Hospital Referral Region (HRR) boundaries: a pilot study in Florida. Annals of GIS 26(3) 251–260.
[18] 
Karrer, B. and Newman, M. E. J. (2011). Stochastic blockmodels and community structure in networks. Physical Review E 83 016107. https://doi.org/10.1103/PhysRevE.83.016107. MR2788206
[19] 
Leskovec, J., Lang, K. J., Dasgupta, A. and Mahoney, M. W. (2009). Community Structure in Large Networks: Natural Cluster Sizes and the Absence of Large Well-Defined Clusters. Internet Mathematics 6(1) 29–123. MR2736090
[20] 
Mucha, P. J., Richardson, T., Macon, K., Porter, M. A. and Onnela, J.-P. (2010). Community structure in time-dependent, multiscale, and multiplex networks. Science 328(5980) 876–878. https://doi.org/10.1126/science.1184819. MR2662590
[21] 
Newman, M. E. (2006). Modularity and community structure in networks. Proceedings of the National Academy of Sciences of the USA 103(23) 8577–8582.
[22] 
Newman, M. (2010) Networks: An Introduction. Oxford University Press, Inc., USA. https://doi.org/10.1093/acprof:oso/9780199206650.001.0001. MR2676073
[23] 
Onnela, J.-P., Saramäki, J., Hyvönen, J., Szabó, G., Lazer, D., Kaski, K., Kertész, J. and Barabási, A.-L. (2007). Structure and tie strengths in mobile communication networks. Proceedings of the National Academy of Sciences 104(18) 7332–7336.
[24] 
Palla, G., Derényi, I., Farkas, I. and Vicsek, T. (2005). Uncovering the overlapping community structure of complex networks in nature and society. Nature 435 814–818.
[25] 
R Core Team (2013). R: A Language and Environment for Statistical Computing. R Foundation for Statistical Computing, Vienna, Austria. http://www.R-project.org/.
[26] 
Schmid, J. S., Taubert, F., Wiegand, T., Sun, I.-F. and Huth, A. (2020). Network science applied to forest megaplots: tropical tree species coexist in small-world networks. Scientific Reports 10 13198.
[27] 
Tandon, A., Albeshri, A., Thayananthan, V., Alhalabi, W., Radicchi, F. and Fortunato, S. (2021). Community detection in networks using graph embeddings. Phys. Rev. E 103 022316.
[28] 
The Center for the Evaluative Clinical Sciences, Dartmouth Medical School (1996) The Dartmouth atlas of health care. American Hospital Publishing, Chicago.
[29] 
Wang, C. and Wang, F. (2022). GIS-automated delineation of hospital service areas in Florida: from Dartmouth method to network community detection methods. Annals of GIS 0(0) 1–17.
[30] 
Wang, C., Tang, W., Sun, B., Fang, J. and Wang, Y. (2015). Review on community detection algorithms in social networks. In 2015 IEEE International Conference on Progress in Informatics and Computing (PIC) 551–555.
[31] 
Wasserman, S. and Faust, K. (1994) Social network analysis: Methods and applications 8. Cambridge university press.
[32] 
Zachary, W. W. (1977). An information flow model for conflict and fission in small groups. Journal of anthropological research 452–473.
[33] 
Zhang, Y., Friend, A. J., Traud, A. L., Porter, M. A., Fowler, J. H. and Mucha, P. J. (2008). Community Structure in Congressional Cosponsorship Networks. Physica A-statistical Mechanics and Its Applications 387 1705–1712.
[34] 
(2020). A Guide for Choosing Community Detection Algorithms in Social Network Studies: The Question Alignment Approach. American Journal Preventative Medicine 59(4) 597–605.

Full article PDF XML
Full article PDF XML

Copyright
© 2024 New England Statistical Society
Open access article under the CC BY license.

Keywords
Modularity Discrete and constrained optimization Patient-sharing network Health care network communities

Funding
Research for the paper was supported by NIH grants U01 AG046830 and P01 AG019783.

Metrics
since December 2021
428

Article info
views

210

Full article
views

190

PDF
downloads

90

XML
downloads


Share


RSS