{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,11]],"date-time":"2025-10-11T01:07:12Z","timestamp":1760144832704,"version":"build-2065373602"},"reference-count":56,"publisher":"MDPI AG","issue":"6","license":[{"start":{"date-parts":[[2024,5,23]],"date-time":"2024-05-23T00:00:00Z","timestamp":1716422400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Algorithms"],"abstract":"<jats:p>This paper presents an approach to community detection in complex networks by simultaneously incorporating a connectivity-based metric and Max-Min Modularity. By leveraging the connectivity-based metric and employing a heuristic algorithm, we develop a novel complementary graph for the Max-Min Modularity that enhances its effectiveness. We formulate community detection as an integer programming problem of an equivalent yet more compact counterpart model of the revised Max-Min Modularity maximization problem. Using a row generation technique alongside the heuristic approach, we then provide a hybrid procedure for near-optimally solving the model and discovering high-quality communities. Through a series of experiments, we demonstrate the success of our algorithm, showcasing its efficiency in detecting communities, particularly in extensive networks.<\/jats:p>","DOI":"10.3390\/a17060226","type":"journal-article","created":{"date-parts":[[2024,5,23]],"date-time":"2024-05-23T09:58:47Z","timestamp":1716458327000},"page":"226","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":2,"title":["Gain and Pain in Graph Partitioning: Finding Accurate Communities in Complex Networks"],"prefix":"10.3390","volume":"17","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-9374-3828","authenticated-orcid":false,"given":"Arman","family":"Ferdowsi","sequence":"first","affiliation":[{"name":"ECS Group, TU Wien, 1040 Vienna, Austria"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-1265-9278","authenticated-orcid":false,"given":"Maryam","family":"Dehghan Chenary","sequence":"additional","affiliation":[{"name":"Department of Business Decisions and Analytics, University of Vienna, 1090 Vienna, Austria"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"1968","published-online":{"date-parts":[[2024,5,23]]},"reference":[{"key":"ref_1","doi-asserted-by":"crossref","unstructured":"Jalali, M., Tsotsalas, M., and W\u00f6ll, C. (2022). MOFSocialNet: Exploiting Metal-Organic Framework Relationships via Social Network Analysis. Nanomaterials, 12.","DOI":"10.3390\/nano12040704"},{"key":"ref_2","doi-asserted-by":"crossref","first-page":"1169","DOI":"10.1007\/s11276-018-01913-4","article-title":"User interest community detection on social media using collaborative filtering","volume":"28","author":"Jiang","year":"2019","journal-title":"Wirel. Netw."},{"key":"ref_3","doi-asserted-by":"crossref","first-page":"542","DOI":"10.1093\/bioinformatics\/btaa775","article-title":"HiSCF: Leveraging higher-order structures for clustering analysis in biological networks","volume":"37","author":"Hu","year":"2021","journal-title":"Bioinformatics"},{"key":"ref_4","doi-asserted-by":"crossref","first-page":"2150214","DOI":"10.1142\/S0217984921502146","article-title":"Effects of link perturbation on network modularity for community detections in complex network systems","volume":"35","author":"Zhao","year":"2021","journal-title":"Mod. Phys. Lett. B"},{"key":"ref_5","doi-asserted-by":"crossref","first-page":"102898","DOI":"10.1016\/j.parco.2022.102898","article-title":"Towards scaling community detection on distributed-memory heterogeneous systems","volume":"111","author":"Gawande","year":"2022","journal-title":"Parallel Comput."},{"key":"ref_6","doi-asserted-by":"crossref","first-page":"2725","DOI":"10.1109\/TSP.2021.3075145","article-title":"Grid-graph signal processing (grid-GSP): A graph signal processing framework for the power grid","volume":"69","author":"Ramakrishna","year":"2021","journal-title":"IEEE Trans. Signal Process."},{"key":"ref_7","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1145\/3444688","article-title":"Community detection in multiplex networks","volume":"54","author":"Magnani","year":"2021","journal-title":"ACM Comput. Surv. (CSUR)"},{"key":"ref_8","doi-asserted-by":"crossref","first-page":"7821","DOI":"10.1073\/pnas.122653799","article-title":"Community structure in social and biological networks","volume":"99","author":"Girvan","year":"2002","journal-title":"Proc. Natl. Acad. Sci. USA"},{"key":"ref_9","doi-asserted-by":"crossref","unstructured":"Chen, J., Za\u00efane, O.R., and Goebel, R. (May, January 30). Detecting communities in social networks using max-min modularity. Proceedings of the 2009 SIAM International Conference on Data Mining, Sparks, NV, USA.","DOI":"10.1137\/1.9781611972795.84"},{"key":"ref_10","doi-asserted-by":"crossref","first-page":"36","DOI":"10.1016\/j.comcom.2018.04.003","article-title":"OLCPM: An online framework for detecting overlapping communities in dynamic social networks","volume":"123","author":"Boudebza","year":"2018","journal-title":"Comput. Commun."},{"key":"ref_11","doi-asserted-by":"crossref","first-page":"P07042","DOI":"10.1088\/1742-5468\/2009\/07\/P07042","article-title":"Quantifying and identifying the overlapping community structure in networks","volume":"2009","author":"Shen","year":"2009","journal-title":"J. Stat. Mech. Theory Exp."},{"key":"ref_12","doi-asserted-by":"crossref","first-page":"349","DOI":"10.1016\/j.procs.2016.06.082","article-title":"An analysis of overlapping community detection algorithms in social networks","volume":"89","author":"Devi","year":"2016","journal-title":"Procedia Comput. Sci."},{"key":"ref_13","doi-asserted-by":"crossref","first-page":"066133","DOI":"10.1103\/PhysRevE.69.066133","article-title":"Fast algorithm for detecting community structure in networks","volume":"69","author":"Newman","year":"2004","journal-title":"Phys. Rev. E"},{"key":"ref_14","doi-asserted-by":"crossref","first-page":"036106","DOI":"10.1103\/PhysRevE.76.036106","article-title":"Near linear time algorithm to detect community structures in large-scale networks","volume":"76","author":"Raghavan","year":"2007","journal-title":"Phys. Rev. E"},{"key":"ref_15","doi-asserted-by":"crossref","unstructured":"Ferdowsi, A., and Chenary, M.D. (2023, January 17\u201320). Toward an Optimal Solution to the Network Partitioning Problem. Proceedings of the 2023 18th Conference on Computer Science and Intelligence Systems (FedCSIS), Warsaw, Poland.","DOI":"10.15439\/2023F2832"},{"key":"ref_16","doi-asserted-by":"crossref","unstructured":"Ferdowsi, A., and Khanteymoori, A. (2021, January 2\u20135). Discovering communities in networks: A linear programming approach using max-min modularity. Proceedings of the 2021 16th Conference on Computer Science and Intelligence Systems (FedCSIS), Sofia, Bulgaria.","DOI":"10.15439\/2021F65"},{"key":"ref_17","doi-asserted-by":"crossref","first-page":"27","DOI":"10.1016\/j.cosrev.2007.05.001","article-title":"Graph clustering","volume":"1","author":"Schaeffer","year":"2007","journal-title":"Comput. Sci. Rev."},{"key":"ref_18","doi-asserted-by":"crossref","unstructured":"Cheikh, S., Sara, B., and Sara, Z. (2020, January 24\u201326). A Hybrid Heuristic Community Detection Approach. Proceedings of the 2020 International Conference on INnovations in Intelligent SysTems and Applications (INISTA), Novi Sad, Serbia.","DOI":"10.1109\/INISTA49547.2020.9194648"},{"key":"ref_19","doi-asserted-by":"crossref","first-page":"114682","DOI":"10.1016\/j.eswa.2021.114682","article-title":"Overlapping community detection by constrained personalized PageRank","volume":"173","author":"Gao","year":"2021","journal-title":"Expert Syst. Appl."},{"key":"ref_20","doi-asserted-by":"crossref","first-page":"117822","DOI":"10.1016\/j.eswa.2022.117822","article-title":"A neighbour-similarity based community discovery algorithm","volume":"206","author":"Sahu","year":"2022","journal-title":"Expert Syst. Appl."},{"key":"ref_21","doi-asserted-by":"crossref","first-page":"46","DOI":"10.1007\/s13278-022-00874-z","article-title":"Tscda: A dynamic two-stage community discovery approach","volume":"12","author":"Ferdowsi","year":"2022","journal-title":"Soc. Netw. Anal. Min."},{"key":"ref_22","first-page":"54","article-title":"Metrics for community analysis: A survey","volume":"50","author":"Chakraborty","year":"2017","journal-title":"ACM Comput. Surv. (CSUR)"},{"key":"ref_23","doi-asserted-by":"crossref","first-page":"2658","DOI":"10.1073\/pnas.0400054101","article-title":"Defining and identifying communities in networks","volume":"101","author":"Radicchi","year":"2004","journal-title":"Proc. Natl. Acad. Sci. USA"},{"key":"ref_24","unstructured":"Wei, Y.C., and Cheng, C.K. (1989, January 5\u20139). Towards efficient hierarchical designs by ratio cut partitioning. Proceedings of the 1989 IEEE International Conference on Computer-Aided Design. Digest of Technical Papers, Santa Clara, CA, USA."},{"key":"ref_25","first-page":"888","article-title":"Normalized cuts and image segmentation","volume":"emph22","author":"Shi","year":"2000","journal-title":"Dep. Pap. (CIS)"},{"key":"ref_26","doi-asserted-by":"crossref","unstructured":"Flake, G.W., Lawrence, S., and Giles, C.L. (2000, January 20\u201323). Efficient identification of web communities. Proceedings of the sixth ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, Boston, MA, USA.","DOI":"10.1145\/347090.347121"},{"key":"ref_27","doi-asserted-by":"crossref","first-page":"8577","DOI":"10.1073\/pnas.0601602103","article-title":"Modularity and community structure in networks","volume":"103","author":"Newman","year":"2006","journal-title":"Proc. Natl. Acad. Sci. USA"},{"key":"ref_28","doi-asserted-by":"crossref","first-page":"105254","DOI":"10.1016\/j.cor.2021.105254","article-title":"Efficient methods for the distance-based critical node detection problem in complex networks","volume":"131","author":"Alozie","year":"2021","journal-title":"Comput. Oper. Res."},{"key":"ref_29","first-page":"1","article-title":"Graph representation learning","volume":"14","author":"Hamilton","year":"2020","journal-title":"Synth. Lect. Artifical Intell. Mach. Learn."},{"key":"ref_30","doi-asserted-by":"crossref","unstructured":"Orman, G.K., and Labatut, V. (2009, January 3\u20135). A comparison of community detection algorithms on artificial networks. Proceedings of the International Conference on Discovery Science, Porto, Portugal.","DOI":"10.1007\/978-3-642-04747-3_20"},{"key":"ref_31","unstructured":"Ferdowsi, A., and Abhari, A. (2020, January 18). Generating high-quality synthetic graphs for community detection in social networks. Proceedings of the 2020 Spring Simulation Conference, Fairfax, VA, USA."},{"key":"ref_32","doi-asserted-by":"crossref","first-page":"544","DOI":"10.1137\/S0097539702416402","article-title":"Local search heuristics for k-median and facility location problems","volume":"33","author":"Arya","year":"2004","journal-title":"SIAM J. Comput."},{"key":"ref_33","unstructured":"Gupta, A., and Tangwongsan, K. (2008). Simpler analyses of local search algorithms for facility location. arXiv."},{"key":"ref_34","doi-asserted-by":"crossref","unstructured":"Ferdowsi, A. (2022, January 4\u20137). An Integer Programming Approach Reinforced by a Message-passing Procedure for Detecting Dense Attributed Subgraphs. Proceedings of the 2022 17th Conference on Computer Science and Intelligence Systems (FedCSIS), Sofia, Bulgaria.","DOI":"10.15439\/2022F64"},{"key":"ref_35","doi-asserted-by":"crossref","unstructured":"Ghosh, S., Halappanavar, M., Tumeo, A., Kalyanaraman, A., Lu, H., Chavarria-Miranda, D., Khan, A., and Gebremedhin, A. (2018, January 21\u201325). Distributed louvain algorithm for graph community detection. Proceedings of the 2018 IEEE international parallel and distributed processing symposium (IPDPS), Vancouver, BC, Canada.","DOI":"10.1109\/IPDPS.2018.00098"},{"key":"ref_36","doi-asserted-by":"crossref","first-page":"113","DOI":"10.1090\/conm\/588\/11705","article-title":"Modularity maximization in networks by variable neighborhood search","volume":"588","author":"Aloise","year":"2012","journal-title":"Graph Partitioning Graph Clust."},{"key":"ref_37","doi-asserted-by":"crossref","first-page":"128903","DOI":"10.1007\/s11467-017-0657-y","article-title":"Modularity-like objective function in annotated networks","volume":"12","author":"Xie","year":"2017","journal-title":"Front. Phys."},{"key":"ref_38","doi-asserted-by":"crossref","first-page":"046110","DOI":"10.1103\/PhysRevE.78.046110","article-title":"Benchmark graphs for testing community detection algorithms","volume":"78","author":"Lancichinetti","year":"2008","journal-title":"Phys. Rev. E"},{"key":"ref_39","doi-asserted-by":"crossref","first-page":"452","DOI":"10.1086\/jar.33.4.3629752","article-title":"An information flow model for conflict and fission in small groups","volume":"33","author":"Zachary","year":"1977","journal-title":"J. Anthropol. Res."},{"key":"ref_40","doi-asserted-by":"crossref","first-page":"355","DOI":"10.1016\/0378-8733(95)00281-2","article-title":"The political network in Mexico","volume":"18","author":"Schmidt","year":"1996","journal-title":"Soc. Netw."},{"key":"ref_41","doi-asserted-by":"crossref","first-page":"396","DOI":"10.1007\/s00265-003-0651-y","article-title":"The bottlenose dolphin community of Doubtful Sound features a large proportion of long-lasting associations","volume":"54","author":"Lusseau","year":"2003","journal-title":"Behav. Ecol. Sociobiol."},{"key":"ref_42","doi-asserted-by":"crossref","first-page":"065103","DOI":"10.1103\/PhysRevE.68.065103","article-title":"Self-similar community structure in a network of human interactions","volume":"68","author":"Guimera","year":"2003","journal-title":"Phys. Rev. E"},{"key":"ref_43","first-page":"35","article-title":"Various approaches of community detection in complex networks: A glance","volume":"8","author":"Mahajan","year":"2016","journal-title":"Int. J. Inf. Technol. Comput. Sci. (IJITCS)"},{"key":"ref_44","doi-asserted-by":"crossref","unstructured":"Meghanathan, N. (2016). A greedy algorithm for neighborhood overlap-based community detection. Algorithms, 9.","DOI":"10.3390\/a9010008"},{"key":"ref_45","unstructured":"Batagelj, V., and Mrvar, A. (2024, May 20). Pajek Datasets. Available online: http:\/\/vlado.fmf.uni-lj.si\/pub\/networks\/data\/."},{"key":"ref_46","doi-asserted-by":"crossref","first-page":"91","DOI":"10.1023\/A:1009615807222","article-title":"A neural network model of caenorhabditis elegans: The circuit of touch sensitivity","volume":"6","author":"Cangelosi","year":"1997","journal-title":"Neural Process. Lett."},{"key":"ref_47","unstructured":"Mrvar, A. (2020). Pajek: Programs for Analysis and Visualization of Very Large Networks: Reference Manual: List of Commands with Short Explanation Version 5.10, University of Ljubljana."},{"key":"ref_48","unstructured":"Chand, S., and Mehta, S. (2017). Hybrid Intelligence for Social Networks, Springer."},{"key":"ref_49","doi-asserted-by":"crossref","first-page":"2","DOI":"10.1145\/1217299.1217301","article-title":"Graph evolution: Densification and shrinking diameters","volume":"1","author":"Leskovec","year":"2007","journal-title":"ACM Trans. Knowl. Discov. Data (TKDD)"},{"key":"ref_50","first-page":"231","article-title":"Detecting communities from networks: Comparison of algorithms on real and synthetic networks","volume":"26","author":"Mkhitaryan","year":"2019","journal-title":"Int. J. Inf. Theor. Appl."},{"key":"ref_51","doi-asserted-by":"crossref","first-page":"181","DOI":"10.1007\/s10115-013-0693-z","article-title":"Defining and evaluating network communities based on ground-truth","volume":"42","author":"Yang","year":"2015","journal-title":"Knowl. Inf. Syst."},{"key":"ref_52","doi-asserted-by":"crossref","unstructured":"Shi, X., Lu, H., He, Y., and He, S. (2015, January 25\u201328). Community detection in social network with pairwisely constrained symmetric non-negative matrix factorization. Proceedings of the 2015 IEEE\/ACM International Conference on Advances in Social Networks Analysis and Mining (ASONAM), Paris, France.","DOI":"10.1145\/2808797.2809383"},{"key":"ref_53","doi-asserted-by":"crossref","first-page":"1387","DOI":"10.1109\/TKDE.2004.74","article-title":"Harp: A practical projected clustering algorithm","volume":"16","author":"Yip","year":"2004","journal-title":"IEEE Trans. Knowl. Data Eng."},{"key":"ref_54","doi-asserted-by":"crossref","first-page":"P09008","DOI":"10.1088\/1742-5468\/2005\/09\/P09008","article-title":"Comparing community structure identification","volume":"2005","author":"Danon","year":"2005","journal-title":"J. Stat. Mech. Theory Exp."},{"key":"ref_55","doi-asserted-by":"crossref","first-page":"1118","DOI":"10.1073\/pnas.0706851105","article-title":"Maps of random walks on complex networks reveal community structure","volume":"105","author":"Rosvall","year":"2008","journal-title":"Proc. Natl. Acad. Sci. USA"},{"key":"ref_56","doi-asserted-by":"crossref","first-page":"23526","DOI":"10.1109\/ACCESS.2020.3045085","article-title":"TNS-LPA: An Improved Label Propagation Algorithm for Community Detection Based on Two-Level Neighbourhood Similarity","volume":"9","author":"Xu","year":"2020","journal-title":"IEEE Access"}],"container-title":["Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/1999-4893\/17\/6\/226\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,10]],"date-time":"2025-10-10T14:47:24Z","timestamp":1760107644000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/1999-4893\/17\/6\/226"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,5,23]]},"references-count":56,"journal-issue":{"issue":"6","published-online":{"date-parts":[[2024,6]]}},"alternative-id":["a17060226"],"URL":"https:\/\/doi.org\/10.3390\/a17060226","relation":{},"ISSN":["1999-4893"],"issn-type":[{"type":"electronic","value":"1999-4893"}],"subject":[],"published":{"date-parts":[[2024,5,23]]}}}