Interest-Aware Seed Node Detection Expands Information Diffusion Across Online Social Networks

Researchers have introduced an interest group-based seed node detection framework that combines the Leiden community detection algorithm with Netdegree Centrality to maximize information diffusion across online social networks. In digital communication platforms, identifying seed users capable of driving information spread represents a core challenge for viral marketing, public announcements, and recommendation systems. Traditional influence maximization techniques typically apply global centrality metrics to the overall network topology, causing selected seeds to cluster within a single dense region and restricting diffusion reach. To address this geographic concentration, the proposed two-stage methodology first segments the directed network into cohesive community structures using the Leiden algorithm and subsequently identifies influential spreaders within each community using Netdegree Centrality. Experimental evaluations on eight benchmark network datasets under the Independent Cascade diffusion model demonstrated that selecting seed nodes across distinct interest groups achieves broad network coverage and avoids redundant influence overlap while maintaining high computational efficiency.

Online social networks serve as central media for disseminating ideas, opinions, behavioral trends, and organizational information across human communities. Within network science, the study of influence maximization focuses on pinpointing an optimal initial set of influential users—termed seed nodes—to trigger wide-ranging information cascades throughout the social fabric. Early foundational research established the mathematical framing of influence maximization under classical propagation models such as the Independent Cascade and Linear Threshold formulations. Subsequent investigations developed scalable heuristic algorithms and topology-based centrality measures, including degree, closeness, betweenness, and eigenvector centrality, to identify influential spreaders. However, these conventional centrality metrics evaluate structural prominence globally without incorporating community partitions. Because global centrality techniques prioritize nodes situated in heavily connected structural cores, they frequently select multiple seed nodes within the same localized cluster. This spatial clustering creates redundant activation among neighboring individuals while leaving separate network regions unreached during early diffusion stages.

Recent investigations into network dynamics indicate that community organization plays a vital role in governing information transmission, as messages typically spread rapidly through cohesive internal ties before traversing boundaries between groups. In recent years, researchers have proposed diverse community-aware strategies, graph optimization routines, deep learning frameworks, and reinforcement learning models to improve diffusion breadth. Despite their conceptual promise, many advanced approaches incur severe computational complexity due to elaborate influence estimation mechanisms and demanding optimization procedures, restricting their practical deployment on large-scale social graphs. Conversely, conventional community detection algorithms often produce partitions that are loosely connected internally. The authors addressed these structural limitations by incorporating the Leiden community detection algorithm, which relies on optimizing the Reichardt and Bornholdt configuration quality. The Leiden algorithm generates well-connected, cohesive subgraphs without excessive fragmentation, providing a scalable foundation for partitioning directed social graphs into structurally dense modular units.

In the formal design of the proposed framework, an online social network is modeled as a directed graph where the vertex set corresponds to network users and directed edges capture directional interactions. The Leiden algorithm partitions the node set into a collection of disjoint interest groups, where each group represents a subset of users exhibiting stronger internal connectivity than external ties. The authors explicitly clarify that the term interest group serves as an application-level interpretation of a structural Leiden community rather than representing semantic user interests or topical preferences. Once these cohesive groups are established, the framework identifies influential seed nodes independently within each interest group using Netdegree Centrality. Defined as the difference between a node’s out-degree and in-degree, Netdegree Centrality quantifies directional influence. Nodes displaying a strictly positive Netdegree score are designated as seed nodes, whereas those with zero or negative scores are classified as non-seed nodes, ensuring that every community possesses locally influential transmitters.

To evaluate the proposed methodology across distinct network sizes and topologies, the researchers conducted empirical experiments using Python within Google Colaboratory across eight benchmark datasets obtained from the Pajek and SNAP repositories. These benchmark networks encompass diverse educational, organizational, political, and social interaction settings. Small-scale datasets include Student Government, a directed interaction network from the University of Ljubljana containing 11 nodes and 41 edges; ModMath, capturing 76 friendship ties among 38 school superintendents; and HiTech, an organizational network recording 147 directed edges among 36 corporate employees. Mid-sized networks include Congress Twitter, representing directed communication across the 117th United States Congress with 475 nodes and 13,289 edges, alongside two institutional communication datasets: Email-EU Core, containing 1,005 nodes and 25,571 edges, and Email URV, documenting 1,133 nodes and 10,902 edges. Large-scale networks comprise the Wikipedia administrator election network Wiki-Vote, featuring 7,115 nodes and 103,689 edges, and the Slashdot social graph, containing 82,168 nodes and 948,464 directed friendship ties.

Information dissemination was simulated using the Independent Cascade model across repeated iterations to quantify empirical reach. Detected seed nodes were initially activated across all identified interest groups, after which each active node received a single opportunity to activate each inactive neighbor with a fixed propagation probability set to 0.10. The cascading process continued iteratively until no further activations occurred. To address the stochastic nature of the diffusion mechanism, simulations were executed across 100 Monte Carlo runs with random seeds, recording total diffusion spread as the count of activated nodes and diffusion coverage as the percentage of activated nodes relative to total network size. Supplementary metrics including non-seed activation and cascade depth were also tracked. Testing on the 11-node Student Government dataset divided the network into three cohesive interest groups at a resolution parameter of 1.0. Comparative evaluations showed that under an equal seed budget, Netdegree Centrality achieved higher mean diffusion spread and coverage than standard degree, betweenness, PageRank, and eigenvector centralities.

In additional experimental evaluations, the framework was applied to the ModMath and HiTech directed datasets, which capture distinct real-world communication dynamics. ModMath models friendship ties among school superintendents, historically used to study the diffusion of modern mathematics teaching methods, whereas HiTech reflects employee relationships during an attempted unionization effort in a small technology company. Experimental settings mirrored the parameters used for the Student Government network. On ModMath, the Leiden algorithm uncovered modular clusters of interacting superintendents, and Netdegree Centrality identified seed nodes within each cluster, including bridge nodes possessing high net outgoing ties that facilitated rapid transmission across separate groups. On HiTech, rather than selecting influential individuals exclusively from a single dominant department as observed in conventional degree-based seeding, the proposed approach distributed seed nodes across distinct employee communication units. This distributed arrangement initiated parallel cascades from multiple organizational subunits, significantly curbing redundant influence overlap among neighboring nodes and markedly enhancing overall network coverage.

To verify the distinct contribution of Netdegree Centrality within the framework, the authors conducted formal ablation analyses across the Student Government, ModMath, and HiTech networks by comparing Leiden combined with Netdegree Centrality against Leiden combined with standard degree centrality. In these ablation trials, community partitions, propagation probabilities, Monte Carlo simulation counts, and seed budgets were maintained strictly identical. Across all three datasets, the Leiden plus Netdegree Centrality pipeline consistently yielded greater diffusion spread and higher diffusion coverage than the Leiden plus Degree variant, validating the specific advantage of ranking nodes by net directional degree. Furthermore, a sensitivity analysis was performed on the HiTech dataset to evaluate stability across varying Leiden resolution parameters and propagation probabilities ranging from 0.05 to 0.25 with a fixed budget of five seed nodes across 100 Monte Carlo runs. The sensitivity trials revealed that community partition counts and configuration quality adjusted systematically with resolution parameters while Leiden plus NDC preserved superior mean diffusion spread throughout tested conditions.

Across the full spectrum of benchmark datasets, the experimental outcomes demonstrated that detected interest groups and identified seed nodes scaled consistently with network dimensions and structural complexity. Compact graphs such as Student Government, ModMath, and HiTech naturally exhibited smaller numbers of detected communities, whereas larger communication structures including Email URV, Email-EU Core, Congress Twitter, Wiki-Vote, and Slashdot formed considerably larger community covers. The distribution of selected seed nodes reflected the underlying modular organization discovered by the Leiden algorithm, avoiding dense clustering while placing influential representatives within every major structural community. Computationally, the methodology exhibited favorable runtime properties across all stages. For a directed graph containing n vertices and m edges, computing Netdegree Centrality for all nodes requires O(n + m) time, selecting nodes with positive Netdegree requires O(n) time, and ranking requires O(n log n) time in the worst case, producing an overall complexity of T_Leiden + O(n + m) + O(n). This streamlined profile avoids the prohibitive training and iterative optimization overhead characteristic of modern graph neural networks.

While confirming the utility of community-aware seed selection, the authors detailed several methodological boundaries alongside relevant avenues for future research. A primary limitation of the current formulation is its static graph assumption, whereas real-world online social networks evolve continuously as users join, depart, and form new associations over time. Extending the proposed framework to dynamic and temporal network structures represents an important future direction for sustaining adaptive seed selection. In addition, future modeling could integrate edge weights, user interaction frequencies, trust relationships, and user activity levels to refine influence estimations. The authors noted that Netdegree Centrality could be integrated with graph neural networks, node embeddings, or alternative propagation frameworks like the Linear Threshold model to examine varied diffusion behaviors. Ultimately, distributing influential seed nodes across structural communities provides practical value across diverse societal applications, including public health awareness campaigns, emergency notifications, viral marketing, recommendation architectures, cyber threat intelligence, and the systematic containment of digital misinformation.

Subject of Research: Community-aware seed node identification for information diffusion in online social networks

Article Title: Interest aware seed node detection for information diffusion in online social networks

Article References: Bhutani, M., Ganai, A. H., Khanday, H. A., Jha, M. K., & Choudhary, A. (2026). Interest aware seed node detection for information diffusion in online social networks. Discover Artificial Intelligence, 6(1), Article 1805. https://doi.org/10.1007/s44163-026-02651-9

Image Credits: AI Generated

DOI: 10.1007/s44163-026-02651-9

Keywords: information diffusion, seed node detection, online social networks, Leiden algorithm, Netdegree Centrality, influence maximization, Independent Cascade model, community detection, Interest, aware, seed, node