From Ants to People: the Vaporization of Social Relationships in Dynamic Community Detection

From Ants to People: the Vaporization of Social Relationships in Dynamic Community Detection Rachid Djerbi1and Mohamed Tahar Bennai1 1Department of Computer Science, Faculty of Sciences, University M’Hamed Bougara of Boumerdes, {r.djerbi, m.bennai}@univ-boumerdes.dz Abstract Community detection in social networks is crucial for understanding social dynamics and interactions. In this paper, we propose LFM2ACO, an algorithm designed to detect dynamic communities by combining the principles of the static Large Families Model (LFM) with those of Ant Colony Optimization (ACO). Inspired by the biological phenomenon of ant colonies, where pheromones guide and reinforce paths to food sources, we model social relationships as dynamic trails that require constant renewal. Just as pheromones evaporate over time unless refreshed by ant activity, social connections weaken without continued interaction. The LFM2ACO algorithm captures this essence, simulating the strengthening of relationships through repeated communication (e.g., messages, likes, comments) and their decay in the absence of such interactions. Comprehensive experiments on real-world social networks, including the Facebook Wall/Links dataset and the Enron email dataset, demonstrate the robustness and efficacy of LFM2ACO in accurately detecting dynamic communities. This work not only enhances the understanding of community evolution but also provides a practical, implemented solution, validated through experimentation, offering valuable insights for future research and development in community detection algorithms. Keywords: Community detection; LFM; Dynamic communities; Ant Colony Optimization (ACO); Social networks; Pheromone; Community evolution. 1 Introduction 1.1 Background Social networks are complex environments modeled by graphs [1]. Analyzing these networks allows the extraction of hidden characteristics, such as community detection [2]. 1.2 Motivation Community detection has received considerable attention, allowing a macroscopic view of network structure. Social networks are dynamic, requiring consideration of their evolution. The LFM algorithm [3] is effective for static communities but doesn’t support dynamic graphs [1]. 1.3 Objectives This study extends the LFM algorithm for dynamic networks using ACO principles. The main objective is to hybridize LFM and ACO for dynamic community detection. Specifically, we aim to: •Study and implement the LFM algorithm for static community detection. •Propose a dynamic extension of LFM based on ACO principles (LFM2ACO). •Evaluate the performance of LFM2ACO in real-world datasets. Section 2 provides related work, Section 3 outlines the methodology, Section 4 presents the experimental setup, Section 5 presents results and analysis, and Section 6 concludes the work. 257 2 Related Work 2.1 Overview Community detection algorithms identify groups of densely connected nodes [4]. Approaches include graph partitioning [5] and hierarchical clustering [6]. Modularity-based methods, like the Louvain algorithm, optimize the modularity score [9]. 2.2 Static vs. Dynamic Algorithms are classified into static [7] and dynamic approaches [10]. Dynamic algorithms account for the temporal evolution of networks [8]. 2.3 Hybrid Approaches Hybrid approaches combine different techniques. There is growing interest in combining metaheuristic algorithms, such as ACO, with traditional algorithms [13,14]. LFM is effective for static communities [3]. This work addresses this limitation by combining LFM with ACO principles. 3 Methodology This section details the hybridization of LFM with ACO for dynamic community detection. 3.1 Large Families Model (LFM) Algorithm The LFM algorithm [3] identifies communities based on ”large families.” The algorithm operates in three main steps: 1. Initial Community Detection 2. Out-Node Integration 3. Community Merging The LFM algorithm uses notations shown in Table 1. Table 1: Notations used in the LFM approach [3]. Notation Description V Set of nodes E Set of edges of the graph G=(V, E) The graph associated with the social network A Adjacency matrix of G A[i, j] Boolean value representing the relationship between nodes i and j MRC Set of maximum connected components MRC(l) The lth MRC The LFM algorithm maximizes the modularity of the resulting community structure but doesn’t account for the temporal evolution of social networks. 3.2 LFM2ACO: Dynamic Extension of LFM using ACO Principles To address the limitations of LFM, we propose LFM2ACO, a dynamic extension of LFM based on ACO principles. The key idea is to use ACO to model the temporal evolution of relationships. Figure 1illustrates the LFM2ACO approach. The LFM2ACO approach consists of the following steps: 1. Data Preprocessing 2. Pheromone Initialization 258 Figure 1: LFM2ACO Approach 3. Ant Colony Optimization 4. Dynamic Community Detection 5. Community Evolution Analysis Figure 2shows an example of how the dynamic network can be represented mathematically and as a 3D matrix. The pheromone update rule is a crucial component: τij(t+ 1) = (1 −ρ)·τij(t) + Pm k=1 ∆τk ij(t) where: * ij(t) is the pheromone value on edge (i, j) at time t * is the pheromone evaporation rate * m is the number of ants * kij(t) is the amount of pheromone deposited by ant k on edge (i, j) at time t Table ?? shows the transcription of the LFM model into ACO terminology. 4 Experimental Setup This section describes the experimental setup used to evaluate the performance of the LFM2ACO approach. 259 Figure 2: LFM2ACO, concept 3D. Table 2: Transcription ACO of the LFM model. LFM Model ACO Terminology Description Social network Set of ants, nests, and food sources Represents the overall social environment Two employees communicating Two adjacent vertices contacted Represents interaction between individuals Week (in our case study) Evaporation of a quantity (Beta) of pheromone Represents the decay of social relationships over time Number of days without contact Number of days of absence Represents the duration of inactivity between individuals 4.1 Dataset Description We used the Facebook Wall/Links dataset [15,16] and the Enron Email dataset [17]. 4.1.1 Facebook Wall/Links Dataset The Facebook Wall/Links dataset contains user-to-user links and user posts. 4.1.2 Enron Email Dataset The Enron Email dataset is a database of emails from the Enron Corporation. We used a subset of the Enron Email dataset consisting of messages exchanged between employees. Figures 3and 4illustrate the datasets. 4.2 Preprocessing and Data Preparation The preprocessing and data preparation steps varied depending on the dataset. For the Enron Email dataset, we performed preprocessing steps to construct a dynamic social network. 4.3 Implementation Environment and Tools Our work was performed on an INTEL CORE™i5 processor with 4GB of memory and a 64-bit Windows operating system. We used text files, a MySQL database, Uwamp, and PHP. 260 Figure 3: Benchmarks used: Facebook Wall on the left and Facebook links on the right. Figure 4: ENRON network before any community detection algorithm was applied. 5 Results and Analysis This section presents and analyzes the results obtained from applying the static LFM algorithm to the Facebook dataset and the dynamic LFM2ACO algorithm to the Enron dataset. 5.1 Static LFM Results on Facebook Dataset The static LFM algorithm was applied to the Facebook Wall/Links dataset. Table 3summarizes the results. Figure 5shows the final community structure obtained for ‘CadjMax‘ = 2. Figure 5: Final distribution result comment for cadjmax=2. 261 Table 3: Summaries of community distributions of each iteration (CadjMax–) with modularity. CadjMax First generation Latest generation Number of out nodes Modularity(Q) 9 40 1 87 5.9799773157978E-17 8 62 1 88 5.9799773157978E-17 7 76 1 89 5.9799773157978E-17 6 102 1 90 5.9799773157978E-17 5 147 2 83 0.17051866319444 4 207 2 83 0.17051866319444 3 283 2 85 0.15957151813272 2 417 3 83 0.15970413773148 5.2 Dynamic LFM2ACO Results on Enron Dataset The dynamic LFM2ACO algorithm was applied to the Enron Email dataset. The algorithm was executed iteratively, updating the pheromone matrix. Figures 6,7,8, and 9illustrate the pheromone update process. Figure 6: Result of the pheromone quantity update, week=46 and year 1998 Figure 7: Result of the pheromone quantity update, week=48 and year 1998 Table 4summarizes the results obtained for week 48 of 1998. Figure 10 shows the community structure obtained for ‘CadjMax‘ = 472. 5.3 Comparison The static LFM algorithm achieved a maximum modularity of 0.17051866319444 on the Facebook dataset, while the dynamic LFM2ACO algorithm achieved a maximum modularity of 0.53652645659928 on the Enron dataset. 262 Figure 8: Result of the pheromone quantity update, week=49 and year 1998. Figure 9: Result of the pheromone quantity update, week=25 and year 2002. 5.4 Discussion The results provide insights into the dynamics of social networks. The dynamic LFM2ACO algorithm captures the community structure in dynamic networks. 6 Conclusion and Future Work This section summarizes the contributions, discusses limitations, and suggests directions for future research. This paper has explored community detection in social networks. The main contributions include the following: •A comprehensive review of existing community detection approaches. •An in-depth study of the LFM algorithm. •The development of LFM2ACO. •An adaptation of the LFM algorithm to handle weighted networks (that we called WLFM for ”Weighted LFM”). •Implementation and evaluation of LFM and LFM2ACO on real-world datasets. This paper has some limitations, like: •The LFM2ACO algorithm was only evaluated on two datasets. •The LFM2ACO algorithm does not explicitly handle overlapping communities. •Scalability to very large networks. Based on these limitations, future research can be identified like: 263 Table 4: Summaries of community distributions of each CadjMAxiteration - with the modularity of the WLFM algorithm. CadjMax Nombre de communauties Modularity (Q) 472 10 0.53652645659928 Figure 10: Graph result for the best distribution CadjMax=472. •Extend the LFM2ACO algorithm to handle overlapping communities. •Improve the scalability of the LFM2ACO algorithm. •Apply the LFM2ACO approach to directed graphs. •Evaluate the performance of the LFM2ACO algorithm on a wider range of datasets. Another AI perspective regarding the use of AI to our original LFM algorithm or the one proposed in this work (LFM2ACO) such as: •Integrating Deep Learning for Predictive Community Dynamics: Leverage temporal graph neural networks (TGNNs) or transformer-based architectures to model the evolution of social interactions, enabling the prediction of future community structures (e.g., births, mergers, or splits) based on historical trajectory patterns and individual behavior embeddings. •Behavior-Aware Forecasting with Reinforcement Learning: Develop hybrid models combining LFM2ACO with deep reinforcement learning (DRL) to simulate adaptive agent behaviors, where AI-driven individuals dynamically switch communities based on learned reward mechanisms reflecting social preferences. •LLM-Enhanced Relationship Semantics: Utilize large language models (LLMs) to analyze textual interaction data (e.g., social media content), extracting semantic signals to enrich edge weighting in WLFM and predict community formation triggers from latent topic shifts. •Neural Attention for Overlap Resolution: Implement multi-head attention mechanisms to detect overlapping community boundaries by learning node-community affiliation probabilities, complementing ACO’s pheromone dynamics with neural interpretability. 264 •Graph Generation for Scenario Projection: Train generative adversarial networks (GANs) or diffusion models on temporal network snapshots to synthesize plausible future graph states, enabling stress-testing of LFM2ACO under predicted social configurations. •Embedding-Driven Scalability: Combine hyperbolic graph embeddings with LFM2ACO’s optimization process to reduce computational complexity in large-scale networks while preserving hierarchical community structures. •Multimodal Fusion for Event Prediction: Architect multimodal pipelines that jointly process network topology (via GNNs), temporal activity sequences (via LSTMs), and user metadata to forecast macro-level community events like mass migrations or influencer-driven splits. References [1] Stanley Wasserman, Katherine Faust, Stanley (University of Illinois Wasserman, UrbanaChampaign) Social Network Analysis: Methods and Applications, Volume 8 de Structural Analysis in the Social Sciences, ISSN 0954-366X, editeur:Cambridge University Press 1994,825 pages. [2] C. Dawson and C. Dawson, “Social network analysis,” A–Z Digit. Res. Methods, pp. 356–361, 2019, doi: 10.4324/9781351044677-54. [3] Djerbi, R., Amad, M., & Imache, R. (2020). A new model for communities’ detection in dynamic social networks inspired from human families. International Journal of Internet Technology and Secured Transactions, 10(1-2), 24-60. [4] S. Fortunato, “Community detection in graphs,” Phys. Rep., vol. 486, no. 3–5, pp. 75– 174, 2010, doi: 10.1016/j.physrep.2009.11.002. [5] M. Girvan and M. E. J. Newman, “Community structure in social and biological networks,” vol. 99, no. 12, 2002. [6] A. Lancichinetti, S. Fortunato, and F. Radicchi, “Benchmark graphs for testing community detection algorithms,” Phys. Rev. E - Stat. Nonlinear, [7] M.NEDIOUI, M´emoire fouille de donn´ee et apprentissage automatique dans les r´eseaux sociaux dynamiques, 2015. [8] NEDIOUI, MED ABDELHAMID. Fouille et apprentissage automatique dans les reseaux sociaux dynamique. 2015. Th‘ese de doctorat. Universit´e Mohamed Khider-Biskra, Alg´erie. [9] Blondel, 2008, V.D. Blondel, J.L. Guillaume, R. Lambiotte et E. Lefebvre. Fast unfolding of communities in large networks. Journal of Statistical Mechanics: Theory and Experiment, vol. 2008, page P10008, 2008. [10] Palla,2007G. Palla, A.L. Barabasi, and T. Vicsek. Quantifying social group evolution. Nature, 446(7136) :664667, 2007. [11] Aynaud T., Fleury E., Guillaume J.-L., Wang Q. (2013). Communities in evolving networks: definitions, detection, and analysis techniques. In Dynamics on and of complex networks, volume 2, p. 159–200. Springer. [12] Z. Chen, K. a. Wilson, Y. Jin, W. Hendrix, and N. F. Samatova. Detecting and Tracking Community Dynamics in Evolutionary Networks. 2010 IEEE International Conference on Data Mining Workshops, pages 318–327, Dec. 2010. [13] Dorigo Gambardella, 1997] Dorigo, M., & Gambardella, L.M. 1997. Ant Colony System: A Cooperative Learning Approach to the Traveling SalesmanProblem. IEEE Transactions on Evolutionary Computation,1(1), 53 66. [14] H.BELLEILI ,2020 Ant ColonyOptimization (ACO) optimisation par colonies de fourmis [15] The Facebook Wall dataset: http://socialnetworks.mpi-sws.mpg.de/data/facebook-wall.txt.gz, Last accessed 24 Mars 2025 265