Hybrid Community-Driven Influence Maximization in Large Social Networks

This section presents a focused review of the extensive influential nodes’ identification literature from the past five years, with particular emphasis on graph-based and community-based approaches most relevant to our research.

Shi et al. [15] proposed a new optimization framework, CycRak, to maximize influence based on cycles ranking in large undirected networks. Unlike traditional centrality measures such as degree, betweenness and closeness centrality selection methods, the researchers prioritized basic cycles and selected influential nodes from these cycles to maximize information spread for CycRak. The study primarily focused on undirected and unweighted networks. The authors acknowledged this limitation and suggested that extension to other network types was necessary.

In the study [16], authors proposed the Out-degree Effective Link (OEL) algorithm by combining out-degree measure with Effective Link to address the problem of information diffusion maximization in dynamic social networks. By incorporating time-sensitive user interactions, this approach enhanced traditional information maximization procedures. The proposed algorithm extended the Independent Cascade (IC) model work based on local topology and effective links, ensuring that information maximization diffusion aligned with temporal constraints of the real-world. The proposed OEL algorithm, which consisted of two stages, first generated a candidate set of seeds using out-degree centrality measure and metrics of effective links to reduce optimization space and in the second stage; it applied a strategy of greedy selection based on submodular properties to spread maximum influence efficiently. The algorithm primarily considered node degree and effective links, but did not take into account other important network structural properties like clustering coefficient or community structure, which could significantly impact influence propagation.

By integrating information from both the neighboring layers of the node and itself, Zhu and Wang [17] proposed a method for influential node identification in complex networks. Unlike existing approaches like k-shell decomposition and degree centrality, which often failed to differentiate nodes effectively, the proposed method outperformed degree centrality with neighboring layer data to quantify influence more accurately. By repeatedly incorporating nearest neighbor information, the approach enhanced precision in ranking influential nodes. The proposed model was evaluated using the SIR model across multiple real-world networks, and results showed that proposed model outperform compared to seven other centrality measures based methods. The method was primarily tested on unweighted and undirected networks with symmetric adjacency matrices. This limits its applicability to more complex network types, such as weighted or directed networks.

Another study was introduced by Zhu and Huang [18] for influential spreaders identification in complex social networks by leveraging spread centrality and path reachability. SpreadRank dynamically selected influential nodes unlike centrality based tradition methods and it minimized influence overlap by optimizing both suppression effectiveness and information diffusion. On real-world networks using the SIR model, the experimental results demonstrated that SpreadRank outperformed the state of the art approaches in both immunization impact and spreading efficiency. For large-scale networks, the method was computationally efficient but it was not applicable to all network topologies because it assumed a limited number of local pivot nodes.

Both the authors [19, 20] proposed a hybrid model called H-GSM (Hybrid Global Structure Model) for identifying influential nodes in complex networks. In the research [19], the authors integrated the GSM (Global Structure Model) framework with local and global centrality measures, specifically degree and K-shell centrality, to enhance influential node identification. They used three real-world networks (Karate, Netscience1, and Router) to evaluate the performance of the H-GSM model. On the other hand, Mukhtar et al. [20] combined the K-shell decomposition approach and degree centrality in their H-GSM method to incorporate both local and global network information for improved identification of influential nodes. They evaluated the performance of their model using the SIR model to simulate the propagation process on six real-world networks. While both studies applied the same core concept of H-GSM, Mukhtar et al. [19] focused more on integrating the GSM framework with centrality measures, whereas Mukhtar et al. [20] emphasized the use of the SIR model for influence propagation simulation.

Zhao et al. [21] introduced a novel method called KPDN for identifying influential nodes in complex networks. The proposed approach combines the correlation characteristics of both local and global features. For the global perspective, the K-shell decomposition was applied to enhance the discriminative degree of each node. Extensive experiments conducted on multiple real-world networks confirmed that KPDN achieved superior performance compared to traditional algorithms, effectively isolating critical nodes, and rapidly fragmented networks. Overall, the authors' method offers a valuable tool for applications where pinpointing influential nodes was crucial, such as epidemic control, network security, and infrastructure stability.

On the other hand, Alasadi and Arb [22] proposed a solution framework for addressing the influence maximization problem. Their framework involved three main phases: Firstly, the community structure was discovered using the link density-based technique clique percolation (CPM), the set of final seed nodes was chosen after the candidate seeds were created in the second step. The IC diffusion model, which simulates influence diffusion in real world network. Experimental findings demonstrated improvement compared to baseline approaches. The authors highlighted the importance of community detection and overlap in improving influence maximization strategies.

Alasadi et al. [23] proposed a graph-based approach was employed to identify influential nodes, with particular emphasis on overlapping nodes across communities to assess their impact on influencer effectiveness. Empirical analyses and simulation experiments revealed a strong correlation between node centrality score and the properties of overlapping nodes, highlighting their critical role in determining influencer performance. Their findings highlight that leveraging overlapping nodes can significantly enhance influence maximization strategies by reducing computational efforts and focusing on nodes with inherently high influence potential.

While there are many studies on the influence maximization problem in OSN, almost all current approaches have important limitations that make them inapplicable in real-world large-scale networks. The traditional centrality measures and their extensions are global and use the entire network without considering the modular nature of social graphs. Moreover, some methods are based on communities and use a localized approach (these can be referred to as community aware methods), but usually do not include the communities' bridges or ways in which communities interact, which are essential for a large information diffusion.

Additionally, some recent hybrid methods limit themselves to using single dimensional or one-dimensional centrality or they are not large directed networks, especially for networks with overlapping community structures or dynamic connectivity. Very few existing works have developed an explicit way of combining multi-criteria influence scoring in communities with bridge detection between communities, and even fewer works have developed a practical and efficient method that is applicable for complex networks.

Our research contributes to the existing literature to fill the gaps identified above by proposing a hybrid influence maximization method that combines community intra-centrality-based influence with inter-community bridging.

The final method represents a comprehensive and powerful approach to social network analysis especially directed complex networks, as it ensures that selected influencers are both locally highly connected and are positioned to contribute to the acceleration of information propagation across the entire network. The inclusion of intra- and inter-influence expands current research and practice in the area of influence maximization while increasing the efficacy and efficiency of research and practice for communities and the overall influence of large networks.

The proposed hybrid seed selection method was tested on three different real-world networks of existing social networks (Soc-Epinions1, Cit-HepTh, and ia-digg-reply); we chose these datasets for their differences in size, community structures, and structural complexity. This way we had a good performance testing ground for determining how well and how fast the hybrid influence maximization works in propagating influence and the results validated the method as superior to baseline methods.

Our experiments across three distinct network datasets showed that the proposed hybrid seed selection model consistently outperformed traditional centrality-based approaches, achieving improvements in influence propagation. The simulation results of the diffusion process under IC and SIR models are presented in Figures 1 and 2, and Tables 2 and 3. We carefully selected parameter values for each model that accurately simulated the flow of information. For the SIR model, we set infection probability (β) to 0.5, and the recovery rate (γ) to 0.01, simulating an epidemic-like diffusion process where nodes stop transmitting influence once they recover [18].

1-1.png

1-2.png

1-3.png

(a)

1-4.png

1-5.png

1-6.png

(b)

1-7.png

1-8.png

1-9.png

(c)

Figure 1. (a) Propagation influence using SIR model, Soc-Epinions1 dataset; (b) Propagation influence using SIR model, Cit-HepTh1 dataset; (c) Propagation influence using SIR model, a-digg-reply dataset

2-1.png

(a)

2-2.png

(b)

2-3.png

(c)

Figure 2. (a) Propagation influence using IC model, Soc-Epinions1 dataset; (b) Propagation influence using IC model, Cit-HepTh1 dataset; (c) Propagation influence using IC model, ia-digg-reply dataset

Table 2. Quantitative comparison of influence diffusion between baseline centrality methods and the proposed approach under IC model

Table 3. Quantitative comparison of influence diffusion between baseline centrality methods and the proposed approach under SIR model

For the IC model, infection probability is determined dynamically based on structural characteristics of the graph [49]. To maintain consistency, we completed 50 iterations for each simulation. Results consistently showed superior performance in networks with overlapping communities due to the integration of intra- and inter-community influence metrics.

In the Soc-Epinions1 network (75,879 nodes, 508,837 edges), which consisted of complex community structure , the hybrid model achieved approximately 65.62% activated nodes after no more than 10 diffusion steps under the IC model much higher than traditional centrality based methods that achieved 62.7% coverage. This represents a clear gain of almost 3 percentage points (≈2,000 additional activated nodes) compared to the strongest baseline, demonstrating its superior ability to penetrate across communities and trigger larger cascades. More significantly, over 70% of the nodes were activated within 6 steps, meaning that not only did the hybrid model account for greater reach, but also greater speed of diffusion. Under the SIR model, the hybrid method once again performed well and induced around 40 to 41% infected nodes, while standard methods achieved 38 to 39% (around 700 additional infected nodes). In addition, our proposed approach consistently outperform baseline methods in terms of inactivated and susceptible nodes under IC and SIR models respectively. Specifically, it achieves the lowest proportion of inactivated or susceptible nodes, indicating that the influence diffusion not only reaches more users but also leaves fewer nodes unaffected. For instance, on this dataset, our approach leaves only 34% and 36% under IC and SIR respectively, compared to mora than 38 to 39% for the baseline centralities. These results demonstrate that our proposed method can identify influential nodes that are highly influential within-communities, and bridge nodes that allow the diffusion to occur across community structures, allowing for the broad influence to be attained rapidly.

Similarly, in the Cit-HepTh network (27,770 nodes, 352,807 edges), which is a highly hierarchical and dense linking citation network, the hybrid approach achieved over 74.34% activated nodes in 12 iterations under IC model, for the baseline it was 59 to 67% (around 4000 additional infected nodes). This was also the case for the SIR model, which, collectively, covered 44% of infected nodes, for the baselines method it was 39 to 41% (around 1600 infected node), all significantly ahead of other examined methods. The hybrid approach also achieved 80% in only six steps, compared to most of the other traditional approaches, which required 10 or more steps. For instance, on this dataset, our approach leaves only 26.2% and 31.3% under IC and SIR respectively, compared to more than 34 to 41% for the baseline centralities. Further justifying the advantage of bridging capacity in seed selection. These outcomes also imply that global bridging is critical for maximizing influence spread in hierarchical structures.

In the ia-digg-reply dataset (30,400 nodes, 86,313 edges) which contains dense and overlapping community structures, the hybrid method continued to perform well, despite being the only overlapping community structure, covering approximately 99.85% activated nodes under the IC model and 62.3% under SIR after 8 iterations, much higher than traditional centrality based methods that achieved 97.5% and 60.5% under IC and SIR respectively, (around 2,600 additional activated nodes under IC and 700 nodes under SIR model). Moreover, our proposed approach consistently outperform baseline methods in terms of inactivated and susceptible nodes under IC and SIR models respectively. Specifically, it achieves the lowest proportion of inactivated nodes. For instance, on this dataset, our approach leaves only 0.17% and 0.6% under IC and SIR respectively, compared to around 3% for the baseline centralities. Because of the large amount of clustering and overlapping in this network, it was considerably more difficult for traditional methods to find influential nodes.

For the recovered (R) state our approach outperform all baseline methods across the three datasets, with higher values on the number of recovered nodes, confirming its effectiveness in maximizing long-term influence coverage.

To support these empirical findings, we further examined the computational time complexity of our proposed approach by analyzing its core components.

First, the community detection step, implemented using the Louvain algorithm, operates with a typical time complexity of O (n log n), where n is the number of nodes, making it efficient for large-scale networks [57]. Next, once communities are detected, influence scores within each community are computed using local metrics such as in and out degree, PageRank, k‐shell and Katz centrality, the original computations for all the nodes has a time complexity of O(m)per iteration and an overall space complexity of O(n+m), where m is the number of edges. The most expensive component is the bridging score, is a combination of betweenness centrality (which can be computed in O(nm) time using Brandes’ algorithm) along with a community diversity metric, but since it only considers community representatives (one per community), the overall cost is still acceptable. Finally, selecting seed nodes involves sorting the top nodes, according to their scores, which can usually be done in O(n log n) time. Our hybrid approach has a time complexity of approximately O(n log n) for large, sparse networks, primarily due to sorting and influence scoring,, and space complexity O(n+m), for the storage of network structures and node metrics. These complexities show the scalability of our method, as well as its practicality for analyzing large social networks.

In this case, the consideration of overlapping community membership and the diversity of nodes influenced greater coverage, the proposed approach outperformed all baseline centrality measures in every experiment in terms of maximizing activations and minimizing uninfluenced nodes. with the hybrid approach achieved a improvements of 2% to +21% percentage point coverage improvement over the baselines. Overall, having community overlap and bridging across communities is important for providing maximal coverage in highly interconnected real-world networks.

Beyond raw coverage, the speeds of influence propagation also showed consistent improvement. For instance, in Cit-HepTh, the hybrid method was at 80% coverage in just six steps, while traditional methods took significantly longer (12 steps). This efficiency is largely due to the hybrid strategy’s capacity to prioritize nodes that are either influential within their local clusters or strategically positioned between communities. These nodes accelerate the spread by enabling influence to rapidly disseminate across the network, thereby avoiding the delays seen in locality constrained diffusion. These differences are not only practically significant but also practically important in environments that have time or urgency concerns such as viral marketing or emergency information sharing. The consistent outperformance of our hybrid approach across diverse network topologies demonstrates that integrating local (intra-community) and global (inter-community) influence factors provides a more comprehensive strategy for influence maximization than methods focusing on isolated centrality measures.

While previous studies such as H-GSM [19, 20] and KPDN [21] incorporated both local and global community information into seed selection, our work extends these approaches by explicitly addressing overlapping community structures and introducing a quantifiable hybrid bridging score that integrates betweenness centrality with community diversity. Similarly, while methods like SpreadRank [18] focus on minimizing redundancy in influence using distance metrics, they overlook the presence and utility of community structures and bridging nodes, limiting their seed selection to local features. OEL [16], although effective in incorporating temporal dynamics, relies solely on local topological features and fails to consider overlapping communities or multi-criteria influence scoring. Our approach improves upon these limitations by combining five normalized centrality measures for intra-community influence and a bridging score for inter-community diffusion, offering a more comprehensive and scalable solution.

In contrast to works like [22, 23], which highlight the importance of overlapping nodes but do not provide strategic integration or quantification of their role, our method not only identifies these nodes but also ensures they actively function as bridges between loosely connected communities. Our findings support the broader understanding that bridge nodes are essential for accelerating information diffusion in complex networks, while challenging the simplifying assumption found in prior work that community boundaries are static or clearly defined. These results demonstrate that our hybrid method addresses both local and global influence propagation and is adaptable to various network topologies, making it a robust advancement in influence maximization research for time-sensitive and large-scale applications such as viral marketing and emergency communication.

These findings are statistically significant, but they also have practical relevance. It is important when using this type of influential users detection technique in applications such as viral marketing, or public awareness campaigns to influence people rapidly and to as many groups of people as possible. By systematically locating both intra-community influential nodes and cross community connectors, our approach is proven to be a more useful method than those using single topological characteristics. Moreover, the method we presented is inherently flexible and transferable to a range of network topologies, providing similarly strong performance in different network types.

That said, the hybrid model’s reliance solely on the network structure presents limitations. The hybrid influence maximization approach effectively identifies influential nodes by analyzing community formations and bridge nodes, which are critical for optimal influence spread. However, the practical issue is that it ignores behavioral factors such as user activity levels, individual user influence style, or content preferences by basing predictions solely on structural properties. Because of this ineffective influence propagation on relevant behavioral factors (characteristics), the activity may not be reflective of reality, potentially constraining the practical application of study for a wide-range of influences where users behavior plays a major role in diffusion success. I would encourage future research to look at dynamic influence modeling to introduce more realism and applicability to interactions that take place in real-time.

Furthermore, this study focused on snapshots of unweighted and static social networks, when in reality social networks are highly dynamic networks with evolving communities, and users interact with different frequencies. Assuming a simplistic diffusion model will limit the realism of the diffusion simulations because user interaction frequency and edges weights are critical to influence propagation, and the use of structural features in the absence of behavioral factors will pre-dispose to bias of seed selection as we cannot consider the activity or content preference of users. Weighted links or dynamic edges could change which nodes bridge a community, and change the timing and scope of the diffusion of influence. Addressing these limitations will be a key focus for future work; including strong data extraction procedures to extract the temporal evolution and dynamics of the community, weighted edges and activity-aware influence measurements, including a wider variety of user features and behaviours [58] instead of using only the network structure would effectively allow for the real-time operationalization of the approach and capture more nuanced diffusion patterns, and enhance the applicability of our approach to real-world contexts like emergency information sharing, viral marketing, and rumor control.

In conclusion, the hybrid community-driven influence maximization method represents a significant advancement in the field of influence maximization. By integrating both local (intra-community) and global (inter-community) influence factors into seed selection, and addressing overlapping communities through a multi-criteria strategy, the approach consistently achieves faster and broader diffusion than existing methods. Its ability to adapt across diverse network structures while maintaining superior performance confirms its value for real-world scenarios requiring efficient and scalable influence propagation.