On maximization of the modularity index in network psychometrics.
Clique partitioning
Modularity index
Network psychometrics
Walktrap algorithm
Journal
Behavior research methods
ISSN: 1554-3528
Titre abrégé: Behav Res Methods
Pays: United States
ID NLM: 101244316
Informations de publication
Date de publication:
10 2023
10 2023
Historique:
accepted:
04
09
2022
medline:
1
11
2023
pubmed:
19
10
2022
entrez:
18
10
2022
Statut:
ppublish
Résumé
The modularity index (Q) is an important criterion for many community detection heuristics used in network psychometrics and its subareas (e.g., exploratory graph analysis). Some heuristics seek to directly maximize Q, whereas others, such as the walktrap algorithm, only use the modularity index post hoc to determine the number of communities. Researchers in network psychometrics have typically not employed methods that are guaranteed to find a partition that maximizes Q, perhaps because of the complexity of the underlying mathematical programming problem. In this paper, for networks of the size commonly encountered in network psychometrics, we explore the utility of finding the partition that maximizes Q via formulation and solution of a clique partitioning problem (CPP). A key benefit of the CPP is that the number of communities is naturally determined by its solution and, therefore, need not be prespecified in advance. The results of two simulation studies comparing maximization of Q to two other methods that seek to maximize modularity (fast greedy and Louvain), as well as one popular method that does not (walktrap algorithm), provide interesting insights as to the relative performances of the methods with respect to identification of the correct number of communities and the recovery of underlying community structure.
Identifiants
pubmed: 36258108
doi: 10.3758/s13428-022-01975-5
pii: 10.3758/s13428-022-01975-5
doi:
Types de publication
Journal Article
Research Support, N.I.H., Extramural
Langues
eng
Sous-ensembles de citation
IM
Pagination
3549-3565Subventions
Organisme : NIAAA NIH HHS
ID : K99 AA028306
Pays : United States
Informations de copyright
© 2022. The Psychonomic Society, Inc.
Références
Aloise, D., Cafieri, S., Caporossi, G., Hansen, P., Perron, S., & Liberti, L. (2010). Column generation algorithms for exact modularity maximization in networks. Physical Review E, 82. https://doi.org/10.1103/PhysRevE.82.046112
Bartholomew, D. J., & Knott, M. (1999). Latent variable models and factor analysis. London, UK: Arnold.
Blondel, V. D., Guillaume, J. L., Lambiotte, R., & Lefebvre, E. (2008). Fast unfolding of communities in large networks. Journal of Statistical Mechanics: Theory and Experiment, 2008(10), P10008 http://stacks.iop.org/1742-5468/2008/i=10/a=P10008 .
Brandes, U., Delling, D., Gaertler, M., Gorke, R., Hoefer, M., Nikoloski, Z., & Wagner, D. (2008). On modularity clustering. IEEE Transactions of Data Knowledge and Engineering, 20(2), 172–188. https://doi.org/10.1109/TKDE.2007.190689
doi: 10.1109/TKDE.2007.190689
Briganti, G., Kempenaers, C., Braun, S., Fried, E. I., & Linkowski, P. (2018). Network analysis of empathy items from the interpersonal reactivity index in 1973 young adults. Psychiatry Research, 265, 87–92. https://doi.org/10.1016/j.psychres.2018.03.082
doi: 10.1016/j.psychres.2018.03.082
pubmed: 29702306
Brusco, M. J. (2006). A repetitive branch-and-bound algorithm for minimum within-cluster sums of squares partitioning. Psychometrika, 71(2), 347–363. https://doi.org/10.1007/s11336-004-1218-1
doi: 10.1007/s11336-004-1218-1
pubmed: 28197962
Brusco, M. J., & Köhn, H.–F. (2009). Clustering qualitative data based on binary equivalence relations: Neighborhood search heuristics for the clique partitioning problem. Psychometrika, 74(4), 685–703.
doi: 10.1007/s11336-009-9126-z
Brusco, M., Steinley, D., & Watts, A. L. (2022). A comparison of spectral clustering and the walktrap algorithm for community detection in network psychometrics. Psychological Methods. Advance online publication. https://doi.org/10.1037/met0000509
Choi, K. W., Batchelder, A. W., Ehlinger, P. P., Safren, S. A., & O’Cleirigh, C. (2017). Applying network analysis to psychological comorbidity and health behavior: Depression, PTSD, and sexual risk in sexual minority men with trauma histories. Journal of Consulting and Clinical Psychology, 85, 1158–1170. https://doi.org/10.1037/ccp0000241
doi: 10.1037/ccp0000241
pubmed: 29189032
pmcid: 5724394
Christensen, A. P. (2018). NetworkToolbox: Methods and measures for brain, cognitive, and psychometric network analysis in R. The R Journal, 10(2), 422–439. Retrieved 2/17/2021 from: https://journal.r-project.org/archive/2018/RJ-2018-065/RJ-2018-065.pdf
Christensen, A. P., Garrido, L. E., & Golino, H. (2021). Comparing community detection algorithms in psychological data: A Monte Carlo simulation. PsyarXiv Preprint. https://doi.org/10.31234/OSF.IO/HZ89E
Csardi, G., & Nepusz, T. (2006). The igraph software package for complex network research. InterJournal Complex Systems, 1695, 1–9.
Dalege, J., Borsboom, D., van Harreveld, F., & van der Maas, H. J. L. (2017). Network analysis on attitudes: A brief tutorial. Social Psychological and Personality Science, 8(5), 528–537. https://doi.org/10.1177/1948550617709827
doi: 10.1177/1948550617709827
pubmed: 28919944
pmcid: 5582642
Dantzig, G. B., Orden, A., & Wolfe, P. (1954). Notes on linear programming: Part I: The generalized simplex method for minimizing a linear form under linear equality constraints. The Rand Corporation.
Davis, M. H. (1980). A multidimensional approach to individual differences in empathy. JSAS Catalog of Selected Documents in Psychology, 10, 85.
Epskamp, S., & Fried, E. I. (2018). A tutorial on regularized partial correlation networks. Psychological Methods, 23(4), 617–634. https://doi.org/10.1037/met0000167
doi: 10.1037/met0000167
pubmed: 29595293
Fan, Y., Li, M., Zhang, P., Wu, J., & Di, Z. (2007). Accuracy and precision of methods for community identification in weighted networks. Physica A, 377, 363–372. https://doi.org/10.1016/j.physa.2006.11.036
doi: 10.1016/j.physa.2006.11.036
Fortunato, S., & Hric, D. (2016). Community detection in networks: A user’s guide. Physics Reports, 659, 1–44. https://doi.org/10.1016/j.physrep.2016.09.002
doi: 10.1016/j.physrep.2016.09.002
Fried, E. I. (2016). R tutorial: How to identify communities of items in networks. Retrieved from http://psych-networks.com/r-tutorial-identify-communities-items-networks/
Friedman, J. H., Hastie, T., & Tibshirani, R. (2008). Sparse inverse covariance estimation with the graphical lasso. Biostatistics, 9(3), 432–441. https://doi.org/10.1093/biostatistics/kxm045
doi: 10.1093/biostatistics/kxm045
pubmed: 18079126
Friedman, J. H., Hastie, T., & Tibshirani, R. (2014). glasso: Graphical lasso-estimation of Gaussian graphical models (R package version 1.8). Retrieved from https://CRAN.R-project.org/package_glasso
Gates, K. M., Henry, T., Steinley, D., & Fair, D. A. (2016). A Monte Carlo evaluation of weighted community detection algorithms. Frontiers in Neuroinformatics, 10, 45. https://doi.org/10.3389/fninf.2016.00045
doi: 10.3389/fninf.2016.00045
pubmed: 27891087
pmcid: 5102890
Girvan, M., & Newman, M. E. J. (2002). Community structure in social and biological networks. Proceedings of the National Academy of Sciences USA, 99(12), 7821–7826. https://doi.org/10.1073/pnas.122653799
doi: 10.1073/pnas.122653799
Golino, H., & Demetriou, A. (2017). Estimating the dimensionality of intelligence like data using exploratory graph analysis. Intelligence, 62, 54–70. https://doi.org/10.1016/j.intell.2017.02.007
doi: 10.1016/j.intell.2017.02.007
Golino, H., Shi, D., Christensen, A. P., Garrido, L. E., Nieto, M. D., Sadana, R., & Martinez-Molina, A. (2020). Investigating the performance of Exploratory Graph Analysis and traditional techniques to identify the number of latent factors: A simulation and tutorial. Psychological Methods, 25(3), 292–320.
doi: 10.1037/met0000255
pubmed: 32191105
pmcid: 7244378
Golino, H. F., & Epskamp, S. (2017). Exploratory graph analysis: A new approach for estimating the number of dimensions in psychological research. PloS One, 12(6), e0174035. https://doi.org/10.1371/journal.pone.0174035
doi: 10.1371/journal.pone.0174035
pubmed: 28594839
pmcid: 5465941
Gomory, R. E. (1958). Outline of an algorithm for integer solutions to linear programs. Bulletin of the American Mathematical Society, 64, 275–278.
doi: 10.1090/S0002-9904-1958-10224-4
Grötschel, M., & Wakabayashi, Y. (1989). A cutting plane algorithm for a clustering problem. Mathematical Programming, 45, 59–96.
doi: 10.1007/BF01589097
Grötschel, M., & Wakabayashi, Y. (1990). Facets of the clique partitioning polytope. Mathematical Programming, 47, 367–387.
doi: 10.1007/BF01580870
Guimerà, R., Sales-Pardo, M., & Amaral, L. A. N. (2004). Modularity from fluctuations in random graphs and complex networks. Physical Review E, 70(2), 025101. https://doi.org/10.1103/PhysRevE.70.025101
doi: 10.1103/PhysRevE.70.025101
Hevey, D. (2018). Network analysis: A brief overview and tutorial. Health Psychology and Behavioral Medicine, 6(1), 301–328. https://doi.org/10.1080/21642850.2018.1521283
doi: 10.1080/21642850.2018.1521283
pubmed: 34040834
pmcid: 8114409
Hoffman, M., Steinley, D., Gates, K. M., Prinstein, M. J., & Brusco, M. J. (2018). Detecting clusters/communities in social networks. Multivariate Behavioral Research, 53(1), 57–73. https://doi.org/10.1080/00273171.2017.1391682
doi: 10.1080/00273171.2017.1391682
pubmed: 29220584
Hubert, L., & Arabie, P. (1985). Comparing partitions. Journal of Classification, 2, 193–218. https://doi.org/10.1007/BF01908075
doi: 10.1007/BF01908075
Isvoranu, A.-M., & Epskamp, S. (in press). Which estimation method to choose in network psychometrics? Deriving guidelines for applied researchers.
Jones, P. J., Mair, P., Riemann, B. C., Mungo, B. L., & McNally, R. J. (2018). A network perspective on comorbid depression in adolescents with obsessive–compulsive disorder. Journal of Anxiety Disorders, 53, 1–8. https://doi.org/10.1016/j.janxdis.2017.09.008
Kehagias, A. (2022). Community Detection Toolbox. ( https://www.mathworks.com/matlabcentral/fileexchange/45867-community-detection-toolbox ), MATLAB Central File Exchange. Retrieved August 24, 2022.
Kendler, K. S., Aggen, S. H., Flint, J., Borsboom, D., & Fried, E. I. (2018). The Centrality of DSM and non-DSM Depressive Symptoms in Han Chinese Women with Major Depression. Journal of Affective Disorders, 227, 739–744. https://doi.org/10.1016/j.jad.2017.11.032
doi: 10.1016/j.jad.2017.11.032
pubmed: 29179144
Krebs, V. (unpublished). http://www.orgnet.com/
Lancichinetti, A., & Fortunato, S. (2009). Community detection algorithms: A comparative analysis. Physical Review E, 80. https://doi.org/10.1103/PhysRevE.80.056117
Land, A. H., & Doig, A. G. (1960). An automatic method of solving discrete programming problems. Econometrica, 28, 497–520.
doi: 10.2307/1910129
Lange, J., & Zickfeld, J. H. (2021). Emotions as overlapping causal networks of emotion components: Implications and methodological approaches. Emotion Review, 13(2), 157–167.
doi: 10.1177/1754073920988787
Lauritzen, S. L. (1996). Graphical Models. Clarendon Press.
Lusseau, D., Schneider, K., Boisseau, O. J., Haase, P., Slooten, E., & Dawson, S. M. (2003). The bottlenose dolphin community of Doubtful Sound features a large proportion of long-lasting associations. Behavioral Ecology and Sociobiology, 54, 396–405.
doi: 10.1007/s00265-003-0651-y
MacQueen, J. B. (1967). Some methods for classification and analysis of multivariate observations. In L. M. Le Cam & J. Neyman (Eds.), Proceedings of the fifth Berkeley symposium on mathematical statistics and probability (Vol. 1, pp. 281–297). University of California Press.
MATLAB. (2020). version 9.8.0 ((R2020a) ed.). The MathWorks Inc..
McElroy, E., & Patalay, P. (2019). In search of disorders: Internalizing symptom networks in a large clinical sample. Journal of Child Psychology and Psychiatry, 60(8), 897–906. https://doi.org/10.1111/jcpp.13044
doi: 10.1111/jcpp.13044
pubmed: 30900257
Newman, M. E. J. (2004a). Fast algorithm for detecting community structure in networks. Physical Review E, 69(6), 066133. https://doi.org/10.1103/PhysRevE.69.066133
doi: 10.1103/PhysRevE.69.066133
Newman, M. E. J. (2004b). Analysis of weighted networks. Physical Review E, 70(5), 056131. https://doi.org/10.1103/PhysRevE.70.056131
doi: 10.1103/PhysRevE.70.056131
Newman, M. E. J. (2006). Modularity and community structure in networks. Proceedings of the National Academy of Sciences U.S.A., 103, 8577–8582. https://doi.org/10.1073/pnas.0601602103
doi: 10.1073/pnas.0601602103
Newman, M. E. J., & Girvan, M. (2004). Finding and evaluating community structure in networks. Physical Review E, 69(2), 026113. https://doi.org/10.1103/PhysRevE.69.026113
doi: 10.1103/PhysRevE.69.026113
Papenberg, M., & Klau, G. W. (2021). Using anticlustering to partition data sets into equivalent parts. Psychological Methods, 26(2), 161–174. https://doi.org/10.1037/met0000301
doi: 10.1037/met0000301
Pons, P., & Latapy, M. (2006). Computing communities in large networks using random walks. Journal of Graph Algorithms and Applications, 10(2), 191–218 http://jgaa.info/accepted/2006/PonsLatapy2006.10.2.pdf
doi: 10.7155/jgaa.00124
Reichardt, J., & Bornholdt, S. (2006). Statistical mechanics of community detection. Physical Review E: Statistics and Nonlinear Soft Matter Physics, 74, 016110–1–016110-14.
doi: 10.1103/PhysRevE.74.016110
Rubinov, M., & Sporns, O. (2010). Complex network measures of brain connectivity: Uses and interpretations. Neuroimage, 52, 1059–1069.
doi: 10.1016/j.neuroimage.2009.10.003
pubmed: 19819337
Steinley, D. (2003). Local optima in K-means clustering: What you don’t know may hurt you. Psychological Methods, 8(3), 294–304. https://doi.org/10.1037/1082-989X.8.3.294
doi: 10.1037/1082-989X.8.3.294
pubmed: 14596492
Steinley, D. (2004). Properties of the Hubert-Arabie adjusted Rand index. Psychological Methods, 9, 386–396. https://doi.org/10.1037/1082-989X.9.3.386
doi: 10.1037/1082-989X.9.3.386
pubmed: 15355155
Steinley, D. (2006). K-means clustering: A half-century synthesis. British Journal of Mathematical and Statistical Psychology, 59(1), 1–34. https://doi.org/10.1348/000711005X48266
doi: 10.1348/000711005X48266
pubmed: 16709277
Steinley, D., & Hubert, L. (2008). Order-constrained solutions in K-means clustering: Even better than being globally optimal. Psychometrika, 73(4), 647–664. https://doi.org/10.1007/s11336-008-9058-z
doi: 10.1007/s11336-008-9058-z
Steinley, D., Brusco, M. J., & Hubert, L. (2016). The variance of the adjusted Rand index. Psychological Methods, 21(2), 261–272. https://doi.org/10.1037/met0000049
doi: 10.1037/met0000049
pubmed: 26881693
Vermunt, J. K., & Magidson, J. (2005). Latent class cluster analysis. In J. A. Hagenaars & A. L. McCutcheon (Eds.), Applied latent class analysis (pp. 89–106). Cambridge University Press.
von Luxburg, U. (2007). A tutorial on spectral clustering. Statistics and Computing, 17(4), 395–416. https://doi.org/10.1007/s11222-007-9033-z
doi: 10.1007/s11222-007-9033-z
Ward, J. H. (1963). Hierarchical grouping to optimize an objective function. Journal of the American Statistical Association, 58(301), 236–244. https://doi.org/10.2307/2282967
doi: 10.2307/2282967
Weidman, A. C., & Tracy, J. L. (2020). Picking up good vibrations: Uncovering the content of distinct positive emotion subjective experience. Emotion, 20(8), 1311–1331.
doi: 10.1037/emo0000677
pubmed: 31535882
Williams, D. R., & Rast, P. (2020). Back to the basics: Rethinking partial correlation network methodology. British Journal of Mathematical and Statistical Psychology, 73(2), 187–212. https://doi.org/10.1111/bmsp.1217
doi: 10.1111/bmsp.1217
pubmed: 31206621
Williams, D. R., Rhemtulla, M., Wysocki, A. C., & Rast, P. (2019). On nonregularized estimation of psychological networks. Multivariate Behavioral Research, 54(5), 719–750. https://doi.org/10.1080/00273171.2019.1575716
doi: 10.1080/00273171.2019.1575716
pubmed: 30957629
pmcid: 6736701
Xu, G., Tsoka, S., & Papageorgiou, L. (2007). Finding community structures in complex networks using mixed integer optimisation. European Physical Journal B, 60, 231–239. https://doi.org/10.1140/epjb/e2007-00331-0
doi: 10.1140/epjb/e2007-00331-0
Zachary, W. (1977). An information flow model for conflict and information fission in small groups. Journal of Anthropological Research, 33, 452–473. https://doi.org/10.1086/jar.33.4.3629752
doi: 10.1086/jar.33.4.3629752