Mapping Unseen Connections: Graph Clustering to Expose User Interaction Patterns
DOI:
https://doi.org/10.62411/faith.3048-3719-77Keywords:
Closeness, Clustering, Communities, Eigenvector Centrality, Social Network, Strong and weak entitiesAbstract
Expanding extensive and intricate social networks has required sophisticated community detection techniques. This study presents an innovative hybrid methodology that utilizes node space similarity and local knowledge to enhance community identification. Node space similarity is defined by integrating eigenvector centrality (EC), which quantifies a node’s influence inside the network, with proximity metrics, such as closeness, to evaluate the connectivity between nodes. This enables us to identify cohorts of individuals with analogous influence and connectivity. We use local knowledge by concentrating on these pivotal nodes' direct connections and attributes, allowing the technique to broaden community discovery (CD) outward effectively. Our five-phase methodology, grounded in an iterative seed expansion algorithm, commences with identifying highly central nodes and progressively develops communities by integrating nodes exhibiting high similarity and local connectivity. The method incorporates graph statistical inference and embedding features to improve accuracy and capture extensive network patterns. This integrated approach facilitates the precise and effective identification of communities within extensive social networks, exceeding the constraints of conventional techniques. This research attained a modularity of 95.05% on the DBLP dataset and 94.50% on the Amazon dataset. This study achieved a Normalized Mutual Information (NMI) of 91.80% on the DBLP dataset, 92.50% on the Amazon dataset, and 90.43% on the football dataset, demonstrating superior performance relative to previous methodologies. The findings indicate that the hybrid method outperforms other recognized methods in large-scale graphs, showcasing notable robustness and efficiency.
Downloads
References
J. O. Bolorunduro and Z. Zou, “Community Detection On Multi-layer Graph using Intra-layer and Inter-layer Linkage Graphs (CDMIILG),” Expert Syst. Appl., vol. 238, p. 121713, Mar. 2024, doi: 10.1016/j.eswa.2023.121713.
C. Yang, J. Liu, Y. Yan, and C. Shi, “FairSIN: Achieving Fairness in Graph Neural Networks through Sensitive Information Neutralization,” Proc. AAAI Conf. Artif. Intell., vol. 38, no. 8, pp. 9241–9249, Mar. 2024, doi: 10.1609/aaai.v38i8.28776.
L. Gadár and J. Abonyi, “Finding multifaceted communities in multiplex networks,” Sci. Rep., vol. 14, no. 1, p. 14521, Jun. 2024, doi: 10.1038/s41598-024-65049-6.
A. P. Christensen, L. E. Garrido, K. Guerra-Peña, and H. Golino, “Comparing community detection algorithms in psychometric networks: A Monte Carlo simulation,” Behav. Res. Methods, vol. 56, no. 3, pp. 1485–1505, Jun. 2023, doi: 10.3758/s13428-023-02106-4.
R. Cavoretto, A. De Rossi, S. Lancellotti, and F. Romaniello, “Node-bound communities for partition of unity interpolation on graphs,” Appl. Math. Comput., vol. 467, p. 128502, Apr. 2024, doi: 10.1016/j.amc.2023.128502.
Y. Xia, Q. Xu, J. Fang, R. Tang, and P. Du, “Bipartite graph-based community-to-community matching in local energy market considering socially networked prosumers,” Appl. Energy, vol. 353, p. 122245, Jan. 2024, doi: 10.1016/j.apenergy.2023.122245.
B. Baruah, M. P. Dutta, S. Banerjee, and D. K. Bhattacharyya, “A novel density based community detection algorithm and its application in detecting potential biomarkers of ESCC,” J. Comput. Sci., vol. 81, p. 102344, Sep. 2024, doi: 10.1016/j.jocs.2024.102344.
J. Zheng, S. Wang, D. Li, and B. Zhang, “Personalized recommendation based on hierarchical interest overlapping community,” Inf. Sci. (Ny)., vol. 479, pp. 55–75, Apr. 2019, doi: 10.1016/j.ins.2018.11.054.
L. S. Yilmaz and A. J. Walhout, “Metabolic network modeling with model organisms,” Curr. Opin. Chem. Biol., vol. 36, pp. 32–39, Feb. 2017, doi: 10.1016/j.cbpa.2016.12.025.
M. E. J. Newman and M. Girvan, “Finding and evaluating community structure in networks,” Phys. Rev. E, vol. 69, no. 2, p. 026113, Feb. 2004, doi: 10.1103/PhysRevE.69.026113.
S. Ahajjam, M. El Haddad, and H. Badir, “A new scalable leader-community detection approach for community detection in social networks,” Soc. Networks, vol. 54, pp. 41–49, Jul. 2018, doi: 10.1016/j.socnet.2017.11.004.
M. Azaouzi, D. Rhouma, and L. Ben Romdhane, “Community detection in large-scale social networks: state-of-the-art and future directions,” Soc. Netw. Anal. Min., vol. 9, no. 1, p. 23, Dec. 2019, doi: 10.1007/s13278-019-0566-x.
M. Rostami, V. Farrahi, S. Ahmadian, S. Mohammad Jafar Jalali, and M. Oussalah, “A novel healthy and time-aware food recommender system using attributed community detection,” Expert Syst. Appl., vol. 221, p. 119719, Jul. 2023, doi: 10.1016/j.eswa.2023.119719.
M. Rostami, M. Oussalah, K. Berahmand, and V. Farrahi, “Community Detection Algorithms in Healthcare Applications: A Systematic Review,” IEEE Access, vol. 11, pp. 30247–30272, 2023, doi: 10.1109/ACCESS.2023.3260652.
M. Rostami, U. Muhammad, S. Forouzandeh, K. Berahmand, V. Farrahi, and M. Oussalah, “An effective explainable food recommendation using deep image clustering and community detection,” Intell. Syst. with Appl., vol. 16, p. 200157, Nov. 2022, doi: 10.1016/j.iswa.2022.200157.
N. Alotaibi and D. Rhouma, “A review on community structures detection in time evolving social networks,” J. King Saud Univ. - Comput. Inf. Sci., vol. 34, no. 8, pp. 5646–5662, Sep. 2022, doi: 10.1016/j.jksuci.2021.08.016.
M. Xu, “Understanding Graph Embedding Methods and Their Applications,” SIAM Rev., vol. 63, no. 4, pp. 825–853, Jan. 2021, doi: 10.1137/20M1386062.
P. Kumar, R. Jain, S. Chaudhary, and S. Kumar, “Solving Community Detection in Social Networks: A comprehensive study,” in 2021 5th International Conference on Computing Methodologies and Communication (ICCMC), Apr. 2021, pp. 239–345. doi: 10.1109/ICCMC51019.2021.9418412.
R. Bhattacharya, N. K. Nagwani, and S. Tripathi, “A community detection model using node embedding approach and graph convolutional network with clustering technique,” Decis. Anal. J., vol. 9, p. 100362, Dec. 2023, doi: 10.1016/j.dajour.2023.100362.
V. A. Traag and L. Šubelj, “Large network community detection by fast label propagation,” Sci. Rep., vol. 13, no. 1, p. 2701, Feb. 2023, doi: 10.1038/s41598-023-29610-z.
M. Rabiei, M. Fartash, and S. Nazari, “A hybrid optimization approach for graph embedding: leveraging Node2Vec and grey wolf optimization,” J. Supercomput., vol. 81, no. 4, p. 514, Feb. 2025, doi: 10.1007/s11227-025-07022-2.
X. Wu et al., “Graph reconstruction and attraction method for community detection,” Appl. Intell., vol. 55, no. 5, p. 357, Apr. 2025, doi: 10.1007/s10489-024-05858-4.
A. Ullah and Y. Meng, “Finding influential nodes via graph embedding and hybrid centrality in complex networks,” Chaos, Solitons & Fractals, vol. 194, p. 116151, May 2025, doi: 10.1016/j.chaos.2025.116151.
Iman Hasan Abed and S. Bahadori, “Using Density Criterion and Increasing Modularity to Detect Communities in Complex Networks,” InfoTech Spectr. Iraqi J. Data Sci., vol. 2, no. 1, pp. 1–15, Jan. 2025, doi: 10.51173/ijds.v2i1.12.
G. Chen and S. Zhou, “A novel overlapping community detection strategy based on Core-Bridge seeds,” Int. J. Mach. Learn. Cybern., vol. 15, no. 6, pp. 2131–2147, Jun. 2024, doi: 10.1007/s13042-023-02020-3.
L. C. Freeman, “A Set of Measures of Centrality Based on Betweenness,” Sociometry, vol. 40, no. 1, p. 35, Mar. 1977, doi: 10.2307/3033543.
L. C. Freeman, “Centrality in social networks conceptual clarification,” Soc. Networks, vol. 1, no. 3, pp. 215–239, Jan. 1978, doi: 10.1016/0378-8733(78)90021-7.
S. P. Borgatti and M. G. Everett, “A Graph-theoretic perspective on centrality,” Soc. Networks, vol. 28, no. 4, pp. 466–484, Oct. 2006, doi: 10.1016/j.socnet.2005.11.005.
A. Bavelas, “Communication Patterns in Task-Oriented Groups,” J. Acoust. Soc. Am., vol. 22, no. 6, pp. 725–730, Nov. 1950, doi: 10.1121/1.1906679.
A. Bihari and M. K. Pandia, “Eigenvector centrality and its application in research professionals’ relationship network,” in 2015 International Conference on Futuristic Trends on Computational Analysis and Knowledge Management (ABLAZE), Feb. 2015, pp. 510–514. doi: 10.1109/ABLAZE.2015.7154915.
H. Shiokawa, Y. Fujiwara, and M. Onizuka, “SCAN++: efficient algorithm for finding clusters, hubs and outliers on large-scale graphs,” Proc. VLDB Endow., vol. 8, no. 11, pp. 1178–1189, Jul. 2015, doi: 10.14778/2809974.2809980.
H. Gmati, A. Mouakher, A. Gonzalez-Pardo, and D. Camacho, “A new algorithm for communities detection in social networks with node attributes,” J. Ambient Intell. Humaniz. Comput., vol. 15, no. 2, pp. 1779–1791, Feb. 2024, doi: 10.1007/s12652-018-1108-5.
L. Guerreiro, F. N. Silva, and D. R. Amancio, “Identifying the perceived local properties of networks reconstructed from biased random walks,” PLoS One, vol. 19, no. 1, p. e0296088, Jan. 2024, doi: 10.1371/journal.pone.0296088.
M. El-Moussaoui, T. Agouti, A. Tikniouine, and M. El Adnani, “A comprehensive literature review on community detection: Approaches and applications,” Procedia Comput. Sci., vol. 151, pp. 295–302, 2019, doi: 10.1016/j.procs.2019.04.042.
J. Mothe, K. Mkhitaryan, and M. Haroutunian, “Community detection: Comparison of state of the art algorithms,” in 2017 Computer Science and Information Technologies (CSIT), Sep. 2017, pp. 125–129. doi: 10.1109/CSITechnol.2017.8312155.
M. E. J. Newman, “Fast algorithm for detecting community structure in networks,” Phys. Rev. E, vol. 69, no. 6, p. 066133, Jun. 2004, doi: 10.1103/PhysRevE.69.066133.
S. R. Chintalapudi and M. H. M. K. Prasad, “Finding research groups using modularity based community detection algorithm,” in 2016 3rd International Conference on Computing for Sustainable Global Development (INDIACom), 2016, pp. 65–69. [Online]. Available: https://ieeexplore.ieee.org/document/7724229
R. K. Behera, S. K. Rath, and M. Jena, “Spanning Tree Based Community Detection Using Min-Max Modularity,” Procedia Comput. Sci., vol. 93, pp. 1070–1076, 2016, doi: 10.1016/j.procs.2016.07.311.
S. G. Krishnan, S. Karthika, and S. Bose, “Detection of communities in dynamic social networks,” in 2016 International Conference on Recent Trends in Information Technology (ICRTIT), Apr. 2016, pp. 1–6. doi: 10.1109/ICRTIT.2016.7569567.
T. Jiang, C. Zhang, H. Zhu, and G. Deng, “Energy-efficient scheduling for a job shop using grey wolf optimization algorithm with double-searching mode,” Math. Probl. Eng., vol. 2018, no. 1, p. 8574892, 2018.
I. Gutiérrez, D. Gómez, J. Castro, and R. Espínola, “A New Community Detection Problem Based on Bipolar Fuzzy Measures,” in Computational Intelligence and Mathematics for Tackling Complex Problems 2, Springer, 2022, pp. 91–99. doi: 10.1007/978-3-030-88817-6_11.
M. Huang, Q. Jiang, Q. Qu, and A. Rasool, “An Overlapping Community Detection Approach in Ego-Splitting Networks Using Symmetric Nonnegative Matrix Factorization,” Symmetry (Basel)., vol. 13, no. 5, p. 869, May 2021, doi: 10.3390/sym13050869.
J. Zhu et al., “A no self-edge stochastic block model and a heuristic algorithm for balanced anti-community detection in networks,” Inf. Sci. (Ny)., vol. 518, pp. 95–112, May 2020, doi: 10.1016/j.ins.2020.01.005.
Y. Yin, Y. Zhao, H. Li, and X. Dong, “Multi-objective evolutionary clustering for large-scale dynamic community detection,” Inf. Sci. (Ny)., vol. 549, pp. 269–287, Mar. 2021, doi: 10.1016/j.ins.2020.11.025.
M. A. Tabarzad and A. Hamzeh, “A heuristic local community detection method (HLCD),” Appl. Intell., vol. 46, no. 1, pp. 62–78, Jan. 2017, doi: 10.1007/s10489-016-0824-9.
X. Zhang, C. Wang, Y. Su, L. Pan, and H.-F. Zhang, “A Fast Overlapping Community Detection Algorithm Based on Weak Cliques for Large-Scale Networks,” IEEE Trans. Comput. Soc. Syst., vol. 4, no. 4, pp. 218–230, Dec. 2017, doi: 10.1109/TCSS.2017.2749282.
X. Zhou, K. Yang, Y. Xie, C. Yang, and T. Huang, “A novel modularity-based discrete state transition algorithm for community detection in networks,” Neurocomputing, vol. 334, pp. 89–99, Mar. 2019, doi: 10.1016/j.neucom.2019.01.009.
V. D. Blondel, J.-L. Guillaume, R. Lambiotte, and E. Lefebvre, “Fast unfolding of communities in large networks,” J. Stat. Mech. Theory Exp., vol. 2008, no. 10, p. P10008, Oct. 2008, doi: 10.1088/1742-5468/2008/10/P10008.
V. A. Traag, L. Waltman, and N. J. Van Eck, “From Louvain to Leiden: guaranteeing well-connected communities,” Sci. Rep., vol. 9, no. 1, pp. 1–12, 2019.
M. Girvan and M. E. J. Newman, “Community structure in social and biological networks,” Proc. Natl. Acad. Sci., vol. 99, no. 12, pp. 7821–7826, Jun. 2002, doi: 10.1073/pnas.122653799.
A. K. Ghoshal, N. Das, S. Bhattacharjee, and G. Chakraborty, “A Fast Parallel Genetic Algorithm Based Approach for Community Detection in Large Networks,” in 2019 11th International Conference on Communication Systems & Networks (COMSNETS), Jan. 2019, pp. 95–101. doi: 10.1109/COMSNETS.2019.8711127.
B. Alhijawi and A. Awajan, “Genetic algorithms: theory, genetic operators, solutions, and applications,” Evol. Intell., vol. 17, no. 3, pp. 1245–1256, Jun. 2024, doi: 10.1007/s12065-023-00822-6.
X. Zeng, W. Wang, C. Chen, and G. G. Yen, “A Consensus Community-Based Particle Swarm Optimization for Dynamic Community Detection,” IEEE Trans. Cybern., vol. 50, no. 6, pp. 2502–2513, Jun. 2020, doi: 10.1109/TCYB.2019.2938895.
H. C. Rustamaji et al., “A network analysis to identify lung cancer comorbid diseases,” Appl. Netw. Sci., vol. 7, no. 1, p. 30, Dec. 2022, doi: 10.1007/s41109-022-00466-y.
S. Fortunato and M. Barthélemy, “Resolution limit in community detection,” Proc. Natl. Acad. Sci., vol. 104, no. 1, pp. 36–41, Jan. 2007, doi: 10.1073/pnas.0605965104.
J.-O. Palacio-Niño and F. Berzal, “Enhancing Community Detection in Networks: A Comparative Analysis of Local Metrics and Hierarchical Algorithms,” arXiv. Aug. 16, 2024. [Online]. Available: http://arxiv.org/abs/2408.09072
J. Guo, P. Singh, and K. E. Bassler, “Resolution limit revisited: community detection using generalized modularity density,” J. Phys. Complex., vol. 4, no. 2, p. 025001, Jun. 2023, doi: 10.1088/2632-072X/acc4a4.
L. Yuan, X. Zhang, Y. Ke, Z. Lu, X. Li, and C. Liu, “Temporal Community Detection and Analysis with Network Embeddings,” Mathematics, vol. 13, no. 5, p. 698, Feb. 2025, doi: 10.3390/math13050698.
A. Miyauchi and Y. Kawase, “Z-Score-Based Modularity for Community Detection in Networks,” PLoS One, vol. 11, no. 1, p. e0147805, Jan. 2016, doi: 10.1371/journal.pone.0147805.
S. Fortunato and D. Hric, “Community detection in networks: A user guide,” Phys. Rep., vol. 659, pp. 1–44, Nov. 2016, doi: 10.1016/j.physrep.2016.09.002.
Y. Farrokhpour Dizaj, S. Lotfi, and J. Hajipour, “A multi-objective social-based algorithm for community detection,” Multimed. Tools Appl., pp. 1–30, Jan. 2025, doi: 10.1007/s11042-024-20555-7.
K. He, Y. Li, S. Soundarajan, and J. E. Hopcroft, “Hidden community detection in social networks,” Inf. Sci. (Ny)., vol. 425, pp. 92–106, Jan. 2018, doi: 10.1016/j.ins.2017.10.019.
S. Chattopadhyay and D. Ganguly, “Node2vec with weak supervision on community structures,” Pattern Recognit. Lett., vol. 150, pp. 147–154, Oct. 2021, doi: 10.1016/j.patrec.2021.06.024.
M. A. Werner, J. de Ron, E. I. Fried, and D. J. Robinaugh, “Iterated community detection in psychological networks.,” Psychol. Methods, Mar. 2025, doi: 10.1037/met0000744.
A. Ibrahem Hafez, A. ella Hassanien, A. A. Fahmy, and M. F. Tolba, “Community detection in social networks by using Bayesian network and Expectation Maximization technique,” in 13th International Conference on Hybrid Intelligent Systems (HIS 2013), Dec. 2013, pp. 209–214. doi: 10.1109/HIS.2013.6920484.
S. Srinivas and C. Rajendran, “Community detection and influential node identification in complex networks using mathematical programming,” Expert Syst. Appl., vol. 135, pp. 296–312, Nov. 2019, doi: 10.1016/j.eswa.2019.05.059.
J. Cheng et al., “Neighbor Similarity Based Agglomerative Method for Community Detection in Networks,” Complexity, vol. 2019, no. 1, p. 8292485, Jan. 2019, doi: 10.1155/2019/8292485.
X. You, Y. Ma, and Z. Liu, “A three-stage algorithm on community detection in social networks,” Knowledge-Based Syst., vol. 187, p. 104822, Jan. 2020, doi: 10.1016/j.knosys.2019.06.030.
N. Kasoro, S. Kasereka, E. Mayogha, H. T. Vinh, and J. Kinganga, “PercoMCV: A hybrid approach of community detection in social networks,” Procedia Comput. Sci., vol. 151, pp. 45–52, 2019, doi: 10.1016/j.procs.2019.04.010.
N. Tahir, A. Hassan, M. Asif, and S. Ahmad, “MCD: Mutually Connected Community Detection using clustering coefficient approach in social networks,” in 2019 2nd International Conference on Communication, Computing and Digital systems (C-CODE), Mar. 2019, pp. 160–165. doi: 10.1109/C-CODE.2019.8680980.
L. Bai, J. Liang, H. Du, and Y. Guo, “A novel community detection algorithm based on simplification of complex networks,” Knowledge-Based Syst., vol. 143, pp. 58–64, 2018.
J. Cao et al., “A unified framework of semi-supervised community detection integrating network topology and node content,” Inf. Sci. (Ny)., vol. 686, p. 121349, 2025.
G. K. Orman, V. Labatut, and H. Cherifi, “Qualitative Comparison of Community Detection Algorithms,” in Digital Information and Communication Technology and Its Applications: International Conference, DICTAP 2011, Dijon, France, June 21-23, 2011, Proceedings, Part II, 2011, pp. 265–279. doi: 10.1007/978-3-642-22027-2_23.
M. R. Hamedani and S.-W. Kim, “JacSim: An accurate and efficient link-based similarity measure in graphs,” Inf. Sci. (Ny)., vol. 414, pp. 203–224, Nov. 2017, doi: 10.1016/j.ins.2017.06.005.
M. E. J. Newman, “Modularity and community structure in networks,” Proc. Natl. Acad. Sci., vol. 103, no. 23, pp. 8577–8582, Jun. 2006, doi: 10.1073/pnas.0601602103.
G. Csardi and T. Nepusz, “The igraph software package for complex network research.” pp. 1–9, 2006.
A. Hagberg, P. J. Swart, and D. A. Schult, “Exploring network structure, dynamics, and function using NetworkX,” 2008.
K. E. Avrachenkov, A. Y. Kondratev, and V. V Mazalov, “Cooperative game theory approaches for network partitioning,” in Computing and Combinatorics: 23rd International Conference, COCOON 2017, Hong Kong, China, August 3-5, 2017, Proceedings 23, 2017, pp. 591–602.
D. Lusseau, K. Schneider, O. J. Boisseau, P. Haase, E. Slooten, and S. M. Dawson, “The bottlenose dolphin community of Doubtful Sound features a large proportion of long-lasting associations,” Behav. Ecol. Sociobiol., vol. 54, no. 4, pp. 396–405, Sep. 2003, doi: 10.1007/s00265-003-0651-y.
J. Yang and J. Leskovec, “Defining and evaluating network communities based on ground-truth,” Knowl. Inf. Syst., vol. 42, no. 1, pp. 181–213, Jan. 2015, doi: 10.1007/s10115-013-0693-z.
L. Jure, “SNAP Datasets: Stanford large network dataset collection,” Stanford Large Network Dataset Collection, 2014. https://snap.stanford.edu/data/
E. Eaton and R. Mansbach, “A spin-glass model for semi-supervised community detection,” in Proceedings of the AAAI Conference on Artificial Intelligence, 2012, vol. 26, no. 1, pp. 900–906.
N. R. Smith, P. N. Zivich, L. M. Frerichs, J. Moody, and A. E. Aiello, “A Guide for Choosing Community Detection Algorithms in Social Network Studies: The Question Alignment Approach,” Am. J. Prev. Med., vol. 59, no. 4, pp. 597–605, Oct. 2020, doi: 10.1016/j.amepre.2020.04.015.
J. Zeng and H. Yu, “A Distributed Infomap Algorithm for Scalable and High-Quality Community Detection,” in Proceedings of the 47th International Conference on Parallel Processing, Aug. 2018, pp. 1–11. doi: 10.1145/3225058.3225137.
S. Fortunato, “Community detection in graphs,” Phys. Rep., vol. 486, no. 3–5, pp. 75–174, Feb. 2010, doi: 10.1016/j.physrep.2009.11.002.
Downloads
Published
How to Cite
Issue
Section
License
Copyright (c) 2025 Haroon Ahmad, Muhammad Sajid, Faheem Mazhar, Muhammad Fuzail
This work is licensed under a Creative Commons Attribution-ShareAlike 4.0 International License.
