# Community Quality and Influence Maximization: An Empirical Study

Motaz Ben Hassine

<figure><img src="image_1.png" /></figure>

## To cite this version:

Motaz Ben Hassine. Community Quality and Influence Maximization: An Empirical Study. 2025. [hal-05385202](https://hal.science/hal-05385202v1)

HAL Id: hal-05385202

https://hal.science/hal-05385202v1

Preprint submitted on 27 Nov 2025

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_2.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
# Community Quality and Influence Maximization:
An Empirical Study

Motaz Ben Hassine¹*

¹*CRIL, University of Artois and CNRS, Lens, France.

Corresponding author(s). E-mail(s): benhassine@cril.fr;

## Abstract

Influence maximization in social networks plays a vital role in applications such as viral marketing, epidemiology, product recommendation, opinion mining, and counter-terrorism. A common approach identifies seed nodes by first detecting disjoint communities and subsequently selecting representative nodes from these communities. However, whether the quality of detected communities consistently affects the spread of influence under the Independent Cascade model remains unclear. This paper addresses this question by extending a previously proposed disjoint community detection method, termed α-Hierarchical Clustering, to the influence maximization problem under the Independent Cascade model. The proposed method is compared with an alternative approach that employs the same seed selection criteria but relies on communities of lower quality obtained through standard Hierarchical Clustering. The former is referred to as *Hierarchical Clustering-based Influence Maximization*, while the latter, which leverages higher-quality community structures to guide seed selection, is termed *α-Hierarchical Clustering-based Influence Maximization*. Extensive experiments are performed on multiple real-world datasets to assess the effectiveness of both methods. The results demonstrate that higher-quality community structures substantially improve information diffusion under the Independent Cascade model, particularly when the propagation probability is low. These findings underscore the critical importance of community quality in guiding effective seed selection for influence maximization in complex networks.

**Keywords:** Influence Maximization, Community detection, Social network, Graph, Seed nodes, Independent Cascade Model
# 1 Introduction

Influence in social networks has gained significant attention in recent years [1]. This growing interest has motivated extensive research aimed at understanding how influence propagates, including the identification of key structural properties such as opinion leaders and communities of interest. To address these challenges, researchers have applied various data mining techniques, including community detection and **Influence Maximization** (IM). The concept of IM was first introduced by Domin-gos et al. [2] in the context of viral marketing. Later, Kempe et al. [3] formalized IM as an optimization problem. Given a positive integer *k*, the goal is to identify a seed set *S* of *k* influential nodes that maximizes the expected spread of influence. Kempe et al. also demonstrated that the IM problem is *NP*-hard and proposed two widely adopted diffusion models: the Linear Threshold Model (LTM) and the Independent Cascade Model (IC). In the IC model, influence spreads over a directed graph *G* = (*V*, *E*) where each edge (*u*, *v*) is associated with an activation probability *p*<sub>*uv*</sub>. Starting from an initial seed set *S*, the diffusion unfolds in discrete time steps. At each step *t*<sub>*i*</sub> (*i* ≥ 0), newly activated nodes are each given one chance to independently activate their currently inactive neighbors. A node *u* attempts to activate a neighbor *v* with probability *p*<sub>*uv*</sub>; if successful, *v* becomes active at time *t*<sub>*i+1*</sub>. Regardless of success or failure, *u* cannot attempt to activate *v* again. The process terminates when no more activations are possible [4]. Despite its importance, IM remains challenging due to both computational complexity and the difficulty of selecting high-quality seed nodes. Kempe et al. [3] proposed the first Greedy algorithm for IM, which iteratively adds the node that provides the largest marginal gain in influence spread. They proved that this algorithm achieves a $(1 - \frac{1}{e}) \approx 0.63$ approximation of the optimal solution. However, the Greedy method is computationally demanding because it repeatedly simulates the diffusion process. To improve efficiency, Leskovec et al. [5] introduced the Cost-Effective Lazy Forward (CELF) algorithm, which accelerates the Greedy procedure by a factor of about 700. Subsequently, Goyal et al. [6] proposed CELF++, which further improves runtime performance. Borgs et al. [7] then introduced the Reverse Influence Sampling (RIS) framework, providing a more scalable alternative to Greedy-based methods. Beyond these approaches, several IM methods rely on community detection. In social networks, a community is a group of users who share common interests or characteristics. In graph theory, it refers to a set of vertices that are densely connected internally but sparsely connected to the rest of the graph. Community-based IM methods exploit these structural properties to guide seed selection. For example, Bouyer et al. [8] proposed a method using overlapping communities to select influential overlapping nodes. Chen et al. [9] introduced the Community-based Influence Maximization (CIM) framework, which uses Hierarchical Clustering (HC) under the Heat Diffusion Model (HDM) [10]. Numerous recent influence maximization approaches rely on community detection as a foundation, including [11–14]. Recently, I improved the HC method by proposing a new similarity measure called α-Structural Similarity (α-2S), which accounts for both common neighbors and the interconnection between them. This led to the development of the α-Hierarchical Clustering (α-HC) algorithm, which replaces the traditional Structural Similarity (2S) measure with α-2S [15]. However, it remained unclear whether the higher-quality community structures
produced by α-HC consistently affect the spread of influence and lead to more effec-
tive seed selection under the Independent Cascade (IC) model [3]. To address this
question, I extend the α-HC framework to the influence maximization problem and
introduce two methods for comparison: *Hierarchical Clustering-based Influence Maxi-
mization* (HCIM), which relies on standard HC with lower-quality communities, and
*α-Hierarchical Clustering-based Influence Maximization* (α-HCIM), which leverages
the higher-quality community structures detected by α-HC to guide seed selection.

The remainder of the paper is structured as follows. Section 2 introduces the formal
notations. Section 3 presents the proposed α-HCIM approach. Section 4 describes my
experiments on real-world social networks. Finally, Section 5 concludes the paper and
outlines future research directions.

## 2 Formal notations

Consider an undirected graph $G = (V, E)$, where $V$ is the set of vertices, and $E$ is the set of edges. The set of **neighbors** of a node $u \in V$ is defined as $Nei(u) = \{v \mid (u, v) \in E\}$. The **degree** of $u \in V$ is then $|Nei(u)|$. $G$ can be divided into numerous subgroups called **communities**, denoted by $C_G = \{c_1, c_2, \dots, c_m\}$. Let $d_{\max}$ be the **maximum degree** of $G$, i.e, $d_{\max} = \max_{|Nei(u)|}\{u \in V\}$. Given a set of nodes $X \subseteq V$, a **subgraph** induced by $X$, denoted as $G_X = (X, E_X)$, is a graph over $X$ s.t. $E_X = \{(u, v) \in E \mid u, v \in X\}$. Besides, let $d_{av}$ be the **average number of neighbors** of all the vertices in $X$, i.e., $d_{av} = \frac{1}{|X|} \sum_{u \in X} |Nei(u)|$. Let $\phi(S)$ represent **the final active set** produced by the stochastic diffusion model, specifically the IC model. Additionally, let denote $\sigma(S) = E(|\phi(S)|)$ as **the influence spread** of set $S$. This indicates the average size of the final active sets the expected size of the final active sets. Let consider $L$ be the path between the nodes $u$ and $v$, then, $d(u, v)$ is called the **distance** between $u$ and $v$ defined as $d(u, v) = \min_{m-1}\{L = (v_1, v_2, \dots, v_m) \text{ s.t. } v_1 = u, v_m = v, \forall 1 \le i < m, (v_i, v_{i+1}) \in E\}$. **The coverage** of a node $u \in V$ is defined as $N^\theta(u) = \{v \in V \mid d(u, v) \le \theta\} \cup \{u\}$. Further, denote $sizeCom(u) = |c|$ where $u \in c$ and $c \in C_G$ the size of the community which $u$ belongs to it. A node $u$ is called an **overlapping node** if $\exists c_i, c_j \in C_G, 1 \le i < j \le m$ s.t. $c_i \cap Nei(u) \ne \emptyset$ and $c_j \cap Nei(u) \ne \emptyset$.

**Definition 1** (Influence Maximization problem [3]). *Given an undirected graph $G = (V, E)$ and $k > 0$. Find a seed set $S \subseteq V$ where $|S| = k$ and $k \ll |V|$ s.t. $\forall S' \subseteq V$ where $|S'| = k$, I have $\sigma(S) \ge \sigma(S')$.*

## 3 An Influence maximization approach based on α-HC

In this section, α-HC method [15] is extended for the influence maximization prob-
lem, referred to α-HCIM. Overlapping nodes can be added in the seed set because
they can link several communities in such a way that it contributes to the effective
propagation of information. However, not all overlapping nodes have the same impor-
tance and then I propose a novel score called **propagator-score** which is described
in the definition that follows.

**Definition 2 (propagator-score).** Let $G = (V, E)$ be an undirected graph. Let $v \in V$ be an overlapping node, and $G_{N^\theta(v)} = (N^\theta(v), E_{N^\theta(v)})$ the subgraph induced by $N^\theta(v)$ then the propagator-score noted score(v) is defined as :

$$ score(v) = \sum_{(u,w) \in E_{N^\theta(v)}} |Nei(u) \cap Nei(w)| \quad (1) $$

**Example 1.** Consider the undirected graph shown in Figure 1.

<figure><img src="image_3.png" /></figure>

Supposing that $v$ and $c$ are overlapping nodes and $\theta = 2$, then:

$$ N^2(v) = \{v, a, e, i, b, m, j, c, d\} $$

$$ N^2(c) = \{c, a, v, f, d, b, g\} $$

then :

$$ score(v) = 0 $$

$$ score(c) = 5 $$

**Fig. 1.** Example for calculating the score of the nodes $v$ and $c$ with $\theta = 2$.

In example 1, based on the scores, node $v$ appears to be more important than node $c$ for selection in the seed set. This is because the score calculates the sum of common neighbors for each pair of nodes linked by an edge in the subgraph induced by $N^2(v)$, which plays a role in mitigating conflicts during the propagation of information. The node with the minimum score is selected to be a candidate in the seed set. When this sum is minimized, it helps to avoid these conflicts. Indeed, let assume that node $c$ is selected in the seed set. Consider a scenario where both nodes $f$ and $d$ simultaneously receive information from node $c$ at time $t$. In this situation, an information propagation conflict arises because node $g$ will subsequently receive information from both nodes $f$ and $d$ at time $t+1$. These conflicts result in a reduction in the number of impacted nodes that successfully receive the information. In the proposed approach, I begin with a set of communities called $C_G$. I then perform a decomposition into two new sets.
The first set consists of communities with a single node, while the second set contains
the remaining communities.

<caption>**Algorithm 1 α-HCIM**</caption>

Require: $G(V, E)$, α, k
Ensure: S
1: $C_G \leftarrow \alpha$-HC
2: $S \leftarrow \emptyset$
3: $C_o \leftarrow \{\forall c_o \in C_G \mid |c_o| = 1\}$
4: $C_b \leftarrow \{\forall c_b \in C_G \mid |c_b| > 1\}$
5: **while** $|S| < k$ and $C_b \neq \emptyset$ **do**
6: &nbsp;&nbsp;&nbsp;&nbsp;**for** $c_b \in C_b$ **do**
7: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;no $\leftarrow \arg\max_{u \in c_b} \sigma(\{u\})$
8: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;$S \leftarrow S \cup \{n\}$
9: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;$c_b \leftarrow c_b \setminus S$
10: &nbsp;&nbsp;&nbsp;&nbsp;**end for**
11: **end while**
12: **while** $|S| < k$ **do**
13: &nbsp;&nbsp;&nbsp;&nbsp;$n \leftarrow \arg\min_{u_o \in c_o, c_o \in C_o} \text{score}(u_o)$
14: &nbsp;&nbsp;&nbsp;&nbsp;$S \leftarrow S \cup \{n\}$
15: &nbsp;&nbsp;&nbsp;&nbsp;$c_o \leftarrow c_o \setminus S$
16: **end while**
17: **while** True **do**
18: &nbsp;&nbsp;&nbsp;&nbsp;$n_1 \leftarrow \arg\min_{u_o \in c_o, c_o \in C_o} \text{score}(u_o)$
19: &nbsp;&nbsp;&nbsp;&nbsp;$\text{spread}_1 \leftarrow \sigma(S)$
20: &nbsp;&nbsp;&nbsp;&nbsp;$n_2 \leftarrow \arg\min_{u \in S} \text{sizeCom}(u)$
21: &nbsp;&nbsp;&nbsp;&nbsp;$S \leftarrow S \setminus \{n_2\}$
22: &nbsp;&nbsp;&nbsp;&nbsp;$S \leftarrow S \cup \{n_1\}$
23: &nbsp;&nbsp;&nbsp;&nbsp;$\text{spread}_2 \leftarrow \sigma(S)$
24: &nbsp;&nbsp;&nbsp;&nbsp;**if** $\text{spread}_2 > \text{spread}_1$ or $C_o = \emptyset$ **then**
25: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;**break**
26: **end if**
27: &nbsp;&nbsp;&nbsp;&nbsp;$S \leftarrow S \setminus \{n_1\}$
28: &nbsp;&nbsp;&nbsp;&nbsp;$S \leftarrow S \cup \{n_2\}$
29: &nbsp;&nbsp;&nbsp;&nbsp;$C_o \leftarrow C_o \setminus \{n_1\}$
30: **end while**
31: **return** S

Subsequently, I apply a sorting operation to the second set, arranging the communities in descending order based on their respective sizes. Significantly, larger communities are of greater importance due to their critical role in information propagation. Following this sorting process, for each community within the second set, I
select the node that maximizes propagation within the subgraph induced by the community set under the IC model. If the size of the seed set remains below $k$, I then select the remaining nodes from the set of single-node communities using the propagator score. A node is chosen if it has the minimum value of the propagator score. After this selection process, I make a small enhancement to the seed set. Specifically, I compute the spreading rate of the seed set. Subsequently, I remove the last node added to the seed set. This node is either selected from the smallest community or the set of single-node communities or selected from larger communities but with less expected information spread value, compared with the nodes selected before it. The removed node is replaced with a node selected from the set of single-node communities. I then recompute the seed set. If the spreading rate is higher than before, I retain the current seed set as the final result. If not, I search for an alternative seed set. It should be noted that the HCIM approach follows exactly the same methodology as α-HCIM, which is formally presented in Algorithm 1, with the sole difference being that communities are detected using the standard HC method instead of α-HC. In other words, for HCIM, $C_G \leftarrow$ HC, whereas for α-HCIM, $C_G \leftarrow$ α-HC.

### Complexity analysis.

The α-HC requires $O(|V|d_{max}^3 + 4|E||X|d_{av} + (|E| + |V|)|V|)$ [15]. Let consider $r$ as the number of Monte Carlo simulations then the IC model takes $O(rk|E|)$ time to estimate the influence spread [16] [17]. Besides, when given a set $X \subset V$, extracting the subgraph induced by $X$ requires $O(|X|^2)$ [18]. Moreover, for the first while loop, let assume that $|S| = k_1$. Let consider $B \subset N^2(u_o)$ and $D \subset N^2(u_o)$ such that $B \neq D$. Furthermore, let consider $m_b$ as the subgraph's edges number induced by $c_b$. Finally, let denote a community $c \in C_G$. Then, α-HCIM requires $O(F)$ where $F = (k_1|C_b|(|c_b|^2 + |c_b|rm_b)) + (k - k_1)|C_o|(|N^2(u_o)|^2 + |E_{N^2(u_o)}|\min(|B| + |D|)) + |C_o|(|C_o|(|N^2(u_o)|^2 + |E_{N^2(u_o)}|\min(|B| + |D|)) + 2kr|E| + k|c||C_G|)$. The complexity is polynomial and is moderately high, which indicates that IM is an $\mathcal{NP}$-hard problem that can always be improved on the runtime side.

## 4 Experiments

This section presents the experiments the influence maximization. Table 1 illustrates the datasets utilized.

<table><caption>**Table 1.** Real-world networks.</caption><thead><tr><td>Datasets</td><td>Nodes/Edges</td><td>Source</td></tr></thead><tbody><tr><td>Karate</td><td>34/78</td><td>[19]</td></tr><tr><td>Dolphin</td><td>62/159</td><td>[20]</td></tr><tr><td>Books</td><td>105/441</td><td>[21]</td></tr><tr><td>Email-Eu-Core</td><td>1005/25571</td><td>[22]</td></tr><tr><td>Facebook-artist</td><td>50515/819306</td><td>[23]</td></tr></tbody></table>
To answer my question, I performed two kinds of experiments. <fnref n="1" /> In the first phase of the experiment, I compared α-HCIM and HCIM, with α set to 1. Both methods employed the same criteria for selecting seed nodes, but HCIM relied on Hierarchical Clustering (HC) [9]. I tested these approaches on two small-world datasets, namely the Karate network and the Dolphin network. I varied the probability parameter *p* of the IC model, from 0.1 to 0.9 while keeping *k* constant where *k* << |V| (specifically, *k* = 4). It should be noted that the number of Monte Carlo simulations for IC model was set to 100 (*r* = 100). For experimental reasons, I fixed *θ* = 2. Additionally, I performed experiments by fixing the value of *p* (specifically, *p* = 0.1) and varying *k* from 4 to 10. In the second phase of the experiment, I set the value of *p* to the lowest probability (*p* = 0.1). My goal was to evaluate the performance of these approaches under the most challenging scenarios of the IC diffusion model, where information propagates very slowly. I compared α-HCIM and HCIM with other datasets. I selected various networks based on their sizes, particularly focusing on the number of edges. In my experiments, I opted for three small-world datasets (Karate, Books, and Dolphin), one moderate dataset (Email-Eu-Core), and one large dataset (Facebook-artist). The selection of Facebook-artist as the large dataset was primarily due to the computational demands of Monte Carlo simulations. To ensure fairness in evaluation across datasets with different sizes, I set *k* = 10. I also compared α-HCIM with two other well-known approaches called CELF [5] and Greedy [3] known for achieving high information spread for an approximation near to 1 - 1/e compared with the optimal solution. My comparison was based on the expected information spread and running time. These experiments were conducted on a machine with a 4-Core E5-2637 CPU (3.5GHz) and 128GB of RAM. It should be noted that the maximum allowable running time delay was 168 hours.

Firstly, I compared 1-HCIM to HCIM in terms of expected information spread and running time. I selected the Karate and the Dolphin networks because 1-HCIM performed better than HCIM in the phase of community detection. I aimed to determine whether the community quality could enhance information spread under the same selection criteria and using the same diffusion model, specifically the IC model. Figures 2, 3, 4, 5, 6, 7, 8, and 9 illustrate the obtained results.

<footnote n="1">¹The source code is available at: https://github.com/2x254/Influence-Maximization</footnote>
<figure><img src="image_4.png" /><figcaption>**Fig. 2.** 1-HCIM vs HCIM on Karate dataset based on expected information spread with k = 4.</figcaption></figure>

<figure><img src="image_5.png" /><figcaption>**Fig. 3.** 1-HCIM vs HCIM on Karate dataset based on running time in seconds with k=4.</figcaption></figure>
<figure><img src="image_6.png" /><figcaption>**Fig. 4.** 1-HCIM vs HCIM on Dolphins dataset based on expected information spread with k = 4.</figcaption></figure>

<figure><img src="image_7.png" /><figcaption>**Fig. 5.** 1-HCIM vs. HCIM on Dolphin dataset based on running time in seconds with k = 4.</figcaption></figure>
<figure><img src="image_8.png" /><figcaption>**Fig. 6.** 1-HCIM vs HCIM on Karate dataset based on expected information spread with *p* = 0.1.</figcaption></figure>

<figure><img src="image_9.png" /><figcaption>**Fig. 7.** 1-HCIM vs HCIM on Karate dataset based on running time in seconds with *p* = 0.1.</figcaption></figure>
<figure><img src="image_10.png" /><figcaption>**Fig. 8.** 1-HCIM vs HCIM on Dolphins dataset based on expected information spread with *p* = 0.1.</figcaption></figure>

<figure><img src="image_11.png" /><figcaption>**Fig. 9.** 1-HCIM vs HCIM on Dolphins dataset based on running time in seconds with *p* = 0.1.</figcaption></figure>

On the information spreading side, histograms reveal that for *k* = 4 and *p* ≤ 0.3, 1-HCIM exhibits a better information spread compared to HCIM, or at least, it matches HCIM’s performance. This finding holds particular interest in the context of the IC model, where information propagation is notably slow. However, if *p* > 0.3 or *k* ≠ 4, 1-HCIM performs similarly overall, occasionally displaying slight improvements or setbacks. On the running time side, HCIM generally outperforms 1-HCIM due to its use of the 1-HC community detection approach, which comes with higher time complexity, particularly the 1-2S similarity.

Despite the significance of running time considerations, my primary focus in this paper is to address the question of whether the enhancement in information spread is contingent on the quality of the identified communities. To gain further insight into
this question, I conducted additional comparisons on different datasets during the second phase of the experiment. Secondly, I maintained *p* = 0.1 and I set *k* = 10. I conducted an initial comparison between 1-HCIM and HCIM. On the aspect of expected information spread, table 2 demonstrates that 1-HCIM outperforms HCIM on the Books network, Dolphin network, and Facebook-artist network with differences of 1, 1, and 888 active nodes, respectively. However, HCIM performs better on the Email network and the Karate network, with differences of 1 and 1, respectively. Based on the results obtained from the first and second phases of the experiment, I can infer that enhancing the community quality can improve information spread, especially when *p* has a lower value within the IC model. However, it's important to note that this improvement may not be consistent across all scenarios. Regarding the running time, HCIM generally outperforms 1-HCIM, but there are instances where 1-HCIM is faster than HCIM, such as on the Dolphin and Email networks.

Furthermore, I conducted a second comparison between 1-HCIM, CELF, and the GREEDY approach, and the results are presented in Tables 3 and 4. In terms of running time, 1-HCIM outperforms all other approaches across all datasets. However, regarding information spread, 1-HCIM exhibits a minor setback with only a modest difference. On the other hand, CELF and GREEDY face scalability issues, as demonstrated by exceeding the timeout during the execution on the Facebook-artist dataset without producing results.

<table><caption>**Table 2.** 1-HCIM vs. HCIM based on expected information spread and running time(s) with *k* = 10 and *p* = 0.1.</caption><thead><tr><th rowspan="2">Datasets</th><th colspan="2">1-HCIM</th><th colspan="2">HCIM</th></tr><tr><th>Running time(s)</th><th>σ(S)</th><th>Running time (s)</th><th>σ(S)</th></tr></thead><tbody><tr><td>Karate</td><td>0.6</td><td>14</td><td><strong>0.4</strong></td><td><strong>15</strong></td></tr><tr><td>Books</td><td>4.4</td><td><strong>32</strong></td><td><strong>2.73</strong></td><td>31</td></tr><tr><td>Dolphin</td><td><strong>0.8</strong></td><td><strong>19</strong></td><td>1.07</td><td>18</td></tr><tr><td>Email-Eu-Core</td><td><strong>551.89</strong></td><td>694</td><td>637.15</td><td><strong>695</strong></td></tr><tr><td>Facebook-artist</td><td>24665.26</td><td><strong>30633</strong></td><td><strong>4484.54</strong></td><td>29745</td></tr></tbody></table>

<table><caption>**Table 3.** 1-HCIM vs. CELF vs. GREEDY based on expected information spread with *k* = 10 and *p* = 0.1.</caption><thead><tr><th rowspan="2">Datasets</th><th colspan="3">Comparison based on σ(S)</th></tr><tr><th>1-HCIM</th><th>CELF</th><th>GREEDY</th></tr></thead><tbody><tr><td>Karate</td><td>14</td><td><strong>15</strong></td><td><strong>15</strong></td></tr><tr><td>Books</td><td>32</td><td><strong>34</strong></td><td><strong>34</strong></td></tr><tr><td>Dolphin</td><td><strong>19</strong></td><td>18</td><td><strong>19</strong></td></tr><tr><td>Email-Eu-Core</td><td>694</td><td><strong>702</strong></td><td><strong>702</strong></td></tr><tr><td>Facebook-artist</td><td><strong>30633</strong></td><td>-</td><td>-</td></tr></tbody></table>
<table><caption>**Table 4.** 1-HCIM vs.CELF vs. GREEDY based on running time(s) with *k* = 10 and *p* = 0.1.</caption><thead><tr><th rowspan="2">Datasets</th><th colspan="3">Comparison based on running time(s)</th></tr><tr><th>1-HCIM</th><th>CELF</th><th>GREEDY</th></tr></thead><tbody><tr><td>Karate</td><td><strong>0.6</strong></td><td>0.99</td><td>6.23</td></tr><tr><td>Books</td><td><strong>4.4</strong></td><td>10.31</td><td>64.43</td></tr><tr><td>Dolphin</td><td><strong>0.8</strong></td><td>2.61</td><td>16.01</td></tr><tr><td>Email-Eu-Core</td><td><strong>551.89</strong></td><td>3419.6</td><td>18402.01</td></tr><tr><td>Facebook-artist</td><td><strong>24665.26</strong></td><td>-</td><td>-</td></tr></tbody></table>

# 5 Conclusion

In summary, in this paper In this work, I extended the α-HC approach to the influence maximization problem under the Independent Cascade (IC) model, resulting in the proposed framework α-HCIM. Experimental results show that, particularly when the IC model operates with a low propagation probability *p*, higher-quality community structures can significantly improve the spread of information. However, this improvement is not guaranteed in all scenarios. As future work, I plan to evaluate the performance of α-HCIM under additional diffusion models, such as the Linear Threshold Model and the Heat Diffusion Model.

# References

[1] Fratiglioni, L., Wang, H.-X., Ericsson, K., Maytan, M. & Winblad, B. Influence of social network on occurrence of dementia: a community-based longitudinal study. *The lancet* **355**, 1315–1319 (2000).

[2] Domingos, P. M. & Richardson, M. Lee, D., Schkolnick, M., Provost, F. J. & Srikant, R. (eds) *Mining the network value of customers*. (eds Lee, D., Schkolnick, M., Provost, F. J. & Srikant, R.) *Proceedings of the seventh ACM SIGKDD international conference on Knowledge discovery and data mining, San Francisco, CA, USA, August 26-29, 2001*, 57–66 (ACM, 2001).

[3] Kempe, D., Kleinberg, J. M. & Tardos, É. Getoor, L., Senator, T. E., Domingos, P. M. & Faloutsos, C. (eds) *Maximizing the spread of influence through a social network*. (eds Getoor, L., Senator, T. E., Domingos, P. M. & Faloutsos, C.) *Proceedings of the Ninth ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, Washington, DC, USA, August 24 - 27, 2003*, 137–146 (ACM, 2003).

[4] Wang, W. & Street, W. N. Modeling and maximizing influence diffusion in social networks for viral marketing. *Applied network science* **3**, 1–26 (2018).

[5] Leskovec, J. et al. Berkhin, P., Caruana, R. & Wu, X. (eds) *Cost-effective outbreak detection in networks*. (eds Berkhin, P., Caruana, R. & Wu, X.) *Proceedings of the*
13th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, San Jose, California, USA, August 12-15, 2007, 420-429 (ACM, 2007).

[6] Goyal, A., Lu, W. & Lakshmanan, L. V. S. Srinivasan, S. et al. (eds) *CELF++: optimizing the greedy algorithm for influence maximization in social networks*. (eds Srinivasan, S. et al.) *Proceedings of the 20th International Conference on World Wide Web, WWW 2011, Hyderabad, India, March 28 - April 1, 2011* (*Companion Volume*), 47-48 (ACM, 2011).

[7] Borgs, C., Brautbar, M., Chayes, J. T. & Lucier, B. Chekuri, C. (ed.) *Maximizing social influence in nearly optimal time*. (ed.Chekuri, C.) *Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2014, Portland, Oregon, USA, January 5-7, 2014*, 946-957 (SIAM, 2014).

[8] Bouyer, A., Beni, H. A., Arasteh, B., Aghaee, Z. & Ghanbarzadeh, R. Fip: A fast overlapping community-based influence maximization algorithm using probability coefficient of global diffusion in social networks. *Expert systems with applications* **213**, 118869 (2023).

[9] Chen, Y.-C., Zhu, W.-Y., Peng, W.-C., Lee, W.-C. & Lee, S.-Y. Cim: community-based influence maximization in social networks. *ACM Transactions on Intelligent Systems and Technology (TIST)* **5**, 1-31 (2014).

[10] Ma, H., Yang, H., Lyu, M. R. & King, I. Shanahan, J. G. et al. (eds) *Mining social networks using heat diffusion processes for marketing candidates selection*. (eds Shanahan, J. G. et al.) *Proceedings of the 17th ACM Conference on Information and Knowledge Management, Napa Valley, California, USA, October 26-30, 2008*, 233-242 (ACM, 2008).

[11] Kazemzadeh, F., Safaei, A. A. & Mirzarezaee, M. Influence maximization in social networks using effective community detection. *Physica A: Statistical Mechanics and its Applications* **598**, 127314 (2022).

[12] Tyagi, A. D. & Asawa, K. Influence maximization in social network using community detection and node modularity. *International Journal of Performability Engineering* **20** (2024).

[13] Devi, S. & Rajalakshmi, M. Community based influencer node identification using hybrid optimisation algorithm in social networks. *Journal of Experimental & Theoretical Artificial Intelligence* **37**, 437-464 (2025).

[14] Ahmad, W. & Wang, B. A learning-based influence maximization framework for complex networks via k-core hierarchies and reinforcement learning. *Expert Systems with Applications* **259**, 125393 (2025).

[15] Hassine, M. B., Jabbour, S., Kmimech, M., Raddaoui, B. & Graiet, M. Wrembel, R., Gamper, J., Kotsis, G., Tjoa, A. M. & Khalil, I. (eds) *A non-overlapping*
*community detection approach based on α-structural similarity.* (eds Wrembel, R., Gamper, J., Kotsis, G., Tjoa, A. M. & Khalil, I.) *Big Data Analytics and Knowledge Discovery - 25th International Conference, Penang, Malaysia, August 28-30, 2023, Proceedings*, 197–211 (Springer, 2023).

[16] Trivedi, N. & Singh, A. Efficient influence maximization in social-networks under independent cascade model. *Procedia Computer Science* **173**, 315–324 (2020).

[17] Ye, Y., Chen, Y. & Han, W. Influence maximization in social networks: theories, methods and challenges. *Array* **100264** (2022).

[18] Martin Jambon. Theoretical computer science: Fast extraction of the edges of an induced subgraph (2015). Available online: https://cstheory.stackexchange.com/questions/33440/fast-extraction-of-the-edges-of-an-induced-subgraph.

[19] Zachary, W. W. An information flow model for conflict and fission in small groups. *Journal of anthropological research* **33** (1977).

[20] Lusseau, D. et al. The bottlenose dolphin community of doubtful sound features a large proportion of long-lasting associations. *Behavioral Ecology and Sociobiology* **54** (2003).

[21] Krebs, V. Books about us politics. unpublished, http://www.orgnet.com (2004).

[22] Leskovec, J. & Krevl, A. Snap datasets: Stanford large network dataset collection at http://snap.stanford.edu/data (2014).

[23] Rozemberczki, B., Davies, R., Sarkar, R. & Sutton, C. Spezzano, F., Chen, W. & Xiao, X. (eds) *GEMSEC: graph embedding with self clustering*. (eds Spezzano, F., Chen, W. & Xiao, X.) *ASONAM '19: International Conference on Advances in Social Networks Analysis and Mining, Vancouver, British Columbia, Canada, 27-30 August, 2019*, 65–72 (ACM, 2019).