A Community-Based Framework for Scalable Influence

Maximization in Social Networks

Sai Sudhan Kunapareddy(2022101052)
Duggi Yashwanth(2022102051)

November 17, 2025

Contents

1 Problem Context 1
1.1 The Era of Social Networks and the Rise of Influence . . . . . . . . . . . . . . . . . . . 1
1.2 Formalizing the Problem: Influence Maximization . . . . . . . . . . . . . . . . . . . . . 1
1.3 Modeling Influence Propagation: Diffusion Models . . . . . . . . . . . . . . . . . . . . 2
1.3.1 Independent Cascade (IC) Model . . . . . . . . . . . . . . . . . . . . . . . . . 2
1.3.2 Linear Threshold (LT) Model . . . . . . . . . . . . . . . . . . . . . . . . . . . 2
1.4 Computational Complexity and Foundational Properties . . . . . . . . . . . . . . . . . . 2
1.4.1 NP-Hardness . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2
1.4.2 Submodularity and the Greedy Approximation . . . . . . . . . . . . . . . . . . 3
1.5 Current Status and the Scalability Bottleneck . . . . . . . . . . . . . . . . . . . . . . . 3

2 Work Completed During the Last Semester 3

2.1 Summary: A Community-Centric Approach . . . . . . . . . . . . . . . . . . . . . . . . 3
2.2 Rationale for Community Detection . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
2.3 Exploration of Community Detection Algorithms . . . . . . . . . . . . . . . . . . . . . 4
2.3.1 Modularity Maximization: The Louvain Method . . . . . . . . . . . . . . . . . 4
2.3.2 Information-Theoretic Approach: Infomap . . . . . . . . . . . . . . . . . . . . 5
2.4 Outcomes and Foundational Lessons . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
2.5 Path Forward . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5

3 Problem Statement for This Semester 6

4 Work Completed Since Last Presentation 6

4.1 A Robust Method for Estimating Influence Spread . . . . . . . . . . . . . . . . . . . . . 6
4.1.1 Independent Cascade with Live-Edge Sampling . . . . . . . . . . . . . . . . . . 6
4.1.2 Pseudocode for Node Influence Estimation . . . . . . . . . . . . . . . . . . . . 7
4.1.3 Complexity Analysis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
4.2 Seed Selection Strategies . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
4.2.1 Greedy Algorithm (Kempe et al., 2003) . . . . . . . . . . . . . . . . . . . . . . 7
4.2.2 CELF (Cost-Effective Lazy Forward Selection) . . . . . . . . . . . . . . . . . . 8
4.2.3 MixedGreedy . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
4.2.4 DegreeDiscountIC . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
4.2.5 Reverse Influence Sampling . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
4.2.6 HITS (Revised explanation and caveats) . . . . . . . . . . . . . . . . . . . . . . 12
4.2.7 PageRank . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13
4.3 Experimental Setup . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14

1
 4.3.1 Experiment 1: PageRank vs Greedy Influence Spread . . . . . . . . . . . . . . . 16
4.3.2 Experiment 2: Evaluate whether high PageRank nodes from a community are
highly influential within that community or outside of it . . . . . . . . . . . . . 16
4.4 Experimental Results . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17
4.4.1 Experiment 1: PageRank vs Greedy Influence Spread . . . . . . . . . . . . . . . 17
4.4.2 Experiment 2: Intra vs Inter-Community Influence . . . . . . . . . . . . . . . . 18
4.5 Lessons Learned . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19

5 Future Plan for This Semester 19

5.1 Refining Seed Allocation among Communities . . . . . . . . . . . . . . . . . . . . . . 19
5.2 Comparative Evaluation Across Algorithms . . . . . . . . . . . . . . . . . . . . . . . . 19
5.3 Scalability Enhancements and Implementation . . . . . . . . . . . . . . . . . . . . . . . 19
5.4 Deliverables . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20

6 PageRank-Based Seed Selection Strategies 21

6.1 PRTH — PageRank with Propagation Probability Threshold (SEKE’21) . . . . . . . . . 21
6.2 PRDD — Hybrid of PRTH and DegreeDiscount (SEKE’21) . . . . . . . . . . . . . . . 22
6.3 HPR-Greedy — High-PageRank Candidate Filtering + Greedy Refinement . . . . . . . 22
6.4 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23

7 Fine-Tuning the Diffusion Probability (p) in the Independent Cascade Model 23

7.1 Component Size Distributions Across (p) . . . . . . . . . . . . . . . . . . . . . . . . . 23
7.2 Choosing (p = 0.05) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25
7.3 Implications for Our Pipeline . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25

8 Experiment 1: Greedy vs. PageRank Seed Selection 25

8.1 Difference from the Previous Experiment . . . . . . . . . . . . . . . . . . . . . . . . . 25
8.2 Global Comparison: Greedy vs. PageRank Across All Communities . . . . . . . . . . . 26
8.3 Community-Level Comparison (Top Two Communities) . . . . . . . . . . . . . . . . . 26
8.4 Conclusions from Experiment 1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27

9 Experiment 2 — Global Benchmarking of Seed Selection Strategies on the DBLP Network 28

9.1 Seed Selection Strategies . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28
9.1.1 Full Greedy (GRE) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29
9.1.2 Community-Based High-Degree (DEG) . . . . . . . . . . . . . . . . . . . . . . 29
9.1.3 Global High-Degree (DEG GLOBAL) . . . . . . . . . . . . . . . . . . . . . . 29
9.1.4 Community-Based PageRank (PG) . . . . . . . . . . . . . . . . . . . . . . . . 29
9.1.5 Greedy over PageRank Candidates (GREEDY PAGERANK) . . . . . . . . . . 29
9.2 Results . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29
9.3 Analysis and Interpretation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30
9.4 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30

10 Related Community-Based Influence Maximization Frameworks 30

10.1 CoFIM: A Community-Based Submodular Surrogate for Scalable Influence Maximization 31
10.2 ILP-Based Community-Aware Influence Maximization . . . . . . . . . . . . . . . . . . 32
1 Problem Context
1.1 The Era of Social Networks and the Rise of Influence
The digital age has fundamentally transformed how humans interact, exchange information, and form
opinions. Online social networks such as Facebook, Twitter (X), LinkedIn, Instagram, and TikTok
are no longer peripheral tools of communication; they are central infrastructures of modern society.
These platforms mediate commerce, politics, education, and culture. From viral marketing campaigns
to coordinated social movements, from pandemic awareness drives to the spread of misinformation,
social networks have repeatedly demonstrated their unprecedented power in shaping human behavior on
a global scale.
From a scientific perspective, these networks are naturally modeled as graphs:

• Nodes (vertices) represent individuals.

• Edges represent relationships, friendships, or follower-followee connections.

The dynamics of information spread in such networks are rarely uniform. Instead, information tends
to propagate through cascades, where one or a few nodes adopt or share some content, which then
spreads recursively through their neighbors. These cascades often begin with a small subset of individu-
als who wield disproportionate influence. Identifying such individuals—the so-called seed nodes—has
become the focal point of a major computational problem: influence maximization.
The problem is not just theoretical. In practice, it enables:

• Viral marketing: selecting initial users to adopt or endorse a product.

• Public health campaigns: targeting key individuals to maximize vaccine awareness.

• Political mobilization: identifying pivotal figures whose engagement can swing group behaviors.

• Combating misinformation: predicting and containing the spread of harmful rumors.

These broad applications underscore why the computational study of influence maximization is both
socially impactful and technically challenging.

1.2 Formalizing the Problem: Influence Maximization

The formal study of influence maximization began with Domingos and Richardson (2001) and was
mathematically solidified by Kempe, Kleinberg, and Tardos (2003). Given a social network graph
G = (V, E), the problem can be defined as follows:

• Let V denote the set of n = |V | nodes.

• Let E denote the set of m = |E| edges.

• A diffusion model specifies how influence propagates.

• For a chosen seed set S ⊆ V , the influence spread σ(S) is the expected number of nodes that
eventually become influenced (activated).

The optimization problem is:

S ∗ = arg max σ(S) (1)
|S|=k

where k is a fixed budget on the number of seeds.

This formulation is deceptively simple. In reality, computing σ(S) is intractable in general net-
works because of probabilistic dependencies and combinatorial explosion. This makes the influence
maximization problem an exemplar of computational difficulty in network science.

1
1.3 Modeling Influence Propagation: Diffusion Models
Central to influence maximization is the diffusion model—the mechanism by which activation spreads
from one node to another. Two models dominate the literature:

1. Independent Cascade (IC) Model

2. Linear Threshold (LT) Model

1.3.1 Independent Cascade (IC) Model

The IC model treats influence spread as a stochastic, discrete-time process.

• At time t = 0, nodes in the seed set S are active.

• When a node u becomes active at time t, it gets one chance to activate each currently inactive
neighbor v.

• The attempt succeeds with probability p(u, v) assigned to edge (u, v).

• If successful, v becomes active at time t + 1. If it fails, u cannot try again.

The process continues until no new activations occur. The final set of activated nodes depends on random
outcomes of all these trials. Thus, σ(S) is defined as the expected number of active nodes across all
possible realizations. This expectation is analytically intractable; hence simulation (e.g., Monte Carlo)
or surrogate methods are required.

1.3.2 Linear Threshold (LT) Model

The LT model, in contrast, captures peer pressure or threshold-based adoption:

• Each node v has a random threshold θv ∼ U [0, 1].

• Each incoming edge (u, v) has an influence weight w(u, v), with the constraint:
X
w(u, v) ≤ 1
u∈N − (v)

• A node v becomes active once the sum of weights from its active neighbors crosses its threshold:
X
w(u, v) ≥ θv
u∈ActiveNeighbors(v)

Like IC, the process unfolds in discrete steps and terminates when no further activations occur.
Both models are NP-hard to optimize, but they reflect different real-world processes. The IC model
is typically used for information spread, while LT is better suited for social adoption behaviors. In
our work, we adopt the IC model, as it naturally maps to community-based influence flows.

1.4 Computational Complexity and Foundational Properties

1.4.1 NP-Hardness
Kempe et al. (2003) showed that maximizing influence under IC and LT models is NP-hard. Even
computing σ(S) for a fixed seed set is #P-hard, meaning exact evaluation is intractable. Brute-force
n


approaches are hopeless. To explore all k possible seed sets is impossible even for moderate networks
(n ∼ 106 , k ∼ 50). Thus, practical algorithms must settle for approximations and heuristics.

2
1.4.2 Submodularity and the Greedy Approximation
A crucial breakthrough is that σ(S) is submodular:

• Submodularity formalizes the principle of diminishing returns.

• For sets A ⊆ B and node v ∈

/ B:

σ(A ∪ {v}) − σ(A) ≥ σ(B ∪ {v}) − σ(B)

Intuitively, adding a new influential node to a small seed set boosts influence more than adding it to an
already large seed set (because of overlaps). Nemhauser et al. (1978) proved that for any monotone
submodular function, a greedy algorithm achieves a (1 − 1/e) approximation—about 63% of optimal.
This result underpins the greedy influence maximization algorithm by Kempe et al.

1.5 Current Status and the Scalability Bottleneck

While greedy is theoretically elegant, it collapses under real-world scale. Why?

• To choose each seed, it must evaluate marginal gain for nearly every node.

• Each evaluation requires estimating σ(S), typically by running thousands of Monte Carlo simu-
lations.

• For networks with millions of nodes and edges, this becomes computationally infeasible.

Subsequent work introduced optimizations:

• CELF (Leskovec et al., 2007) reduces redundant influence evaluations.

• Heuristics (degree, centrality) offer speed but no guarantees.

• RIS (Borgs et al., 2014) achieves near-optimal guarantees with sampling.

Yet, the core bottleneck remains scalability. None of these approaches scale gracefully to graphs with
billions of edges. This challenge motivated our community-based hypothesis: if influence is mostly
local within dense communities, then decomposing the graph reduces problem size drastically. Instead
of working with G as a whole, we optimize within smaller communities, aiming to retain effectiveness
while scaling to very large networks.

2 Work Completed During the Last Semester

2.1 Summary: A Community-Centric Approach
In the first phase of our work, our attention was directed toward problem scoping and structural de-
composition of the influence maximization task. We recognized early that the intractability of existing
methods stemmed not only from the complexity of the diffusion models but also from the global scale
at which the problem was being tackled.
Our central hypothesis was that influence is predominantly localized within communities. In
sociological terms, individuals are most influenced by those with whom they share strong ties—close
friends, colleagues, and interest groups—rather than distant acquaintances. Translating this into graph-
theoretic terms, the densely connected subgraphs (communities) of a large network act as natural
basins of influence. Thus, partitioning the network into communities offers two-fold benefits:

1. Reduction in search space: Instead of solving a k-seed optimization across the entire graph of n
nodes, we solve smaller optimization problems on communities of size nc ≪ n.

3
 2. Conceptual alignment: The communities defined by strong intra-connectivity map directly to
the observed patterns of localized influence cascades.

Hence, our work during the first evaluation focused primarily on community detection—identifying an
algorithm that is both computationally efficient and theoretically aligned with information flow.

2.2 Rationale for Community Detection

Community detection is a well-studied domain within network science. Social networks rarely form a
uniform mesh of interactions; rather, they exhibit modular structure, where groups of nodes are tightly
interconnected internally but sparsely connected to the rest of the graph. This modularity plays a crucial
role in influence spread:

• Within a community, influence flows rapidly due to dense connectivity.

• Crossing between communities requires traversing bridge edges, which are relatively few and act
as bottlenecks.

By explicitly modeling this structure, we transform the influence maximization problem:

[
G = (V, E) → {C1 , C2 , . . . , Cm }, Ci = V
i

Now, instead of analyzing influence globally, we can analyze influence locally within each Ci . If the
hypothesis holds that intra-community influence dominates, then the union of top seeds from each com-
munity provides a near-optimal approximation of global influence while drastically reducing runtime.

2.3 Exploration of Community Detection Algorithms

We investigated multiple approaches to community detection, evaluating their theoretical underpinnings
and computational properties.

2.3.1 Modularity Maximization: The Louvain Method

• Motivation: Introduced by Newman and Girvan, modularity measures the density of intra-community
edges relative to a null random graph. A high modularity score indicates a strong community
structure.

• Algorithm: The Louvain method greedily optimizes modularity in two stages:

1. Each node is initially assigned to its own community. Iteratively, a node is moved to a
neighboring community if it yields the greatest modularity gain.
2. Communities are collapsed into supernodes, forming a coarser graph. The process repeats
hierarchically.

• Complexity: Roughly O(m) per pass, scalable to networks with hundreds of millions of edges.

• Limitations: Suffers from the resolution limit problem, often merging small but meaningful
communities into larger ones.

4
2.3.2 Information-Theoretic Approach: Infomap
• Motivation: Based on information theory, Infomap seeks to minimize the description length
of a random walk on the graph. If a walker spends a long time inside a community before
crossing to another, using two-level codebooks (one for intra-community moves, another for
inter-community moves) compresses the trajectory. The optimal partition minimizes this map
equation:
Xm
L(M ) = q↷ H(Q) + pi⟳ H(P i ) (2)
i=1

where:

– q↷ : probability of exiting a community,

– H(Q): entropy of inter-community moves,
– pi⟳ : probability of being within community i,
– H(P i ): entropy of intra-community moves.

• Algorithm: Infomap uses simulated annealing and greedy local moves to minimize the map equa-
tion.

• Complexity: O(m) in practice, with excellent scalability.

• Strengths: Detects fine-grained communities that modularity-based methods may miss. Aligns
conceptually with information flow, making it highly relevant for influence maximization.

2.4 Outcomes and Foundational Lessons

From this exploration, we concluded that Infomap is the most suitable community detection method for
our framework. It offers both scalability and conceptual alignment: by compressing random walks, it
directly reflects the pathways through which influence spreads.
Key lessons:

• Structural decomposition matters: Simply partitioning the graph reduces computational over-
head by orders of magnitude.

• Community detection is not neutral: The choice of algorithm shapes the downstream influence
maximization results, since different methods may partition the graph differently.

• Resolution vs scalability: Infomap balances detection of small communities with the ability to
scale to large datasets, which modularity-based approaches struggle with.

2.5 Path Forward

Having settled on Infomap, the logical next step was to focus on influence computation within com-
munities. This raised key questions for the second phase:

1. How can influence spread be estimated efficiently under the Independent Cascade model?

2. Which seed selection strategies are both scalable and effective proxies for true influence?

3. Can intra-community seed selection be validated as a correct approximation to global influence

maximization?

These questions framed the problem statement for the current semester, guiding us from theory to
implementation.

5
3 Problem Statement for This Semester
Building upon our previous work of decomposing the global influence maximization problem into
community-level subproblems using the Infomap algorithm, the focus of the current semester is to de-
sign, implement, and evaluate the operational core of our scalable framework. The specific objectives
are threefold.
First, we aim to establish a robust methodology for estimating influence spread within communities
under the Independent Cascade (IC) model. Since exact computation of expected influence is #P-hard,
we will employ efficient simulation-based techniques, particularly Monte Carlo sampling via live-edge
graph construction, to approximate the spread.
Second, we will explore and compare a range of seed selection strategies—from classical greedy al-
gorithms (Kempe et al.) and their optimizations (CELF, NewGreedy, MixedGreedy), to modern scalable
approaches like Reverse Influence Sampling (RIS), and heuristics such as HITS and PageRank. The
objective is to evaluate their trade-offs in terms of accuracy, scalability, and alignment with community-
based influence.
Finally, we will design experiments to validate our core hypothesis: that seeds selected within
communities exert influence predominantly inside their own community rather than across communities.
Confirming this will justify the decomposition strategy and provide a practical pipeline for scalable
influence maximization in large-scale networks.

4 Work Completed Since Last Presentation

4.1 A Robust Method for Estimating Influence Spread
The central challenge of influence maximization is estimating the influence spread σ(S), the expected
number of nodes activated given a seed set S. Since exact computation is intractable, we adopted the
Independent Cascade (IC) model with Monte Carlo simulations.

4.1.1 Independent Cascade with Live-Edge Sampling

Instead of simulating activations step-by-step, we employ the live-edge graph formulation:

• For each edge (u, v) in E, include it in a sampled graph G′ with probability p(u, v).

• Influence of a node u in G′ equals the size of its connected component.

• Averaging across R such samples approximates σ({u}).

This approach reduces diffusion to a deterministic reachability problem within each sampled graph.
Mathematical Estimator:
R
1 X
σ({u}) ≈ size(CCi (u)) (3)
R
i=1

where CCi (u) is the connected component of u in the i-th sampled graph.

6
4.1.2 Pseudocode for Node Influence Estimation

Algorithm 1 EstimateNodeInfluence
0: Input: G = (V, E), node u, probabilities P , simulations R
0: Output: estimated influence
0: total ← 0
0: for i = 1 to R do
0: E′ ← ∅
0: for each edge (x, y) in E do
0: if random() < P (x, y) then
0: add (x, y) to E ′
0: end if
0: end for
0: G′ ← (V, E ′ )
0: component size ← BFS(G′ , u)
0: total ← total + component size
0: end for
0: return total/R =0

4.1.3 Complexity Analysis

• Sampling edges: O(mc ) per simulation.

• BFS/DFS traversal: O(nc + mc ).

• Total for R simulations: O(R · (nc + mc ))

where nc and mc are nodes/edges in a community. Since nc ≪ n, this is computationally feasible within
communities, validating our divide-and-conquer scalability strategy.

4.2 Seed Selection Strategies

With a method for influence estimation, the next step is to evaluate algorithms for seed set selection.
We studied a range of approaches from foundational greedy algorithms to modern scalable heuristics.

4.2.1 Greedy Algorithm (Kempe et al., 2003)

Motivation Provides the best-known theoretical guarantee: a (1 − 1/e) ≈ 63% approximation of
the optimal spread, due to the submodularity of σ(S).

Algorithm Description Start with empty seed set S. Iteratively add the node u that maximizes the
marginal gain:
u∗ = arg max σ(S ∪ {u}) − σ(S)
 
u∈V \S

Repeat until |S| = k.

7
Algorithm 2 GreedySeedSelection
0: Input: G = (V, E), k, σ (influence estimator)
0: Output: Seed set S
0: S←∅
0: for i = 1 to k do
0: best node ← null
0: max gain ← −∞
0: for each u in V \ S do
0: gain ← σ(S ∪ {u}) − σ(S)
0: if gain > max gain then
0: max gain ← gain
0: best node ← u
0: end if
0: end for
0: S ← S ∪ {best node}
0: end for
0: return S =0

Time Complexity O(k · n · R · (n + m)), which is computationally prohibitive.

Context in Our Framework Serves as a benchmark to compare scalable heuristics against.

4.2.2 CELF (Cost-Effective Lazy Forward Selection)

Motivation The CELF algorithm (Leskovec et al., 2007) addresses the inefficiency of the Greedy
algorithm by exploiting submodularity to reduce redundant computations.

Algorithm Description CELF maintains a priority queue of nodes, sorted by their marginal gains.
Instead of recomputing gains for all nodes at every iteration, it uses ”lazy evaluation” to ensure only a
fraction of marginal gains need to be recomputed.

8
Algorithm 3 CELF Seed Selection
0: Input: G = (V, E), k, σ (influence estimator)
0: Output: Seed set S
0: S←∅
0: Q ← empty max-priority queue
0: for each node u in V do
0: gain ← σ({u}) {Initial marginal gain}
0: insert (u, gain, 0) into Q {(node, gain, last update iteration)}
0: end for
0: for i = 1 to k do
0: repeat
0: (u, gain, iter) ← extract max(Q)
0: if iter == i − 1 then
0: S ← S ∪ {u} {Gain is valid}
0: break
0: else
0: new gain ← σ(S ∪ {u}) − σ(S)
0: insert (u, new gain, i − 1) back into Q
0: end if
0: until false
0: end for
0: return S =0

Complexity Analysis In practice, CELF reduces the number of influence evaluations by an order of
magnitude, achieving up to a 700x speedup over vanilla greedy while selecting exactly the same seed
sets.

Context in Our Framework Serves as an upper baseline for efficiency vs accuracy trade-offs.
While still computationally heavy, it demonstrates the power of lazy evaluation.

4.2.3 NewGreedy, MixedGreedy, and DegreeDiscount (Expanded)

Motivation: Classical greedy maximization under the IC model is accurate but computationally in-
tractable for large graphs. Chen, Wang, and Yang (2009) proposed optimizations and heuristics that
reduce runtime substantially while maintaining near-greedy influence spread.

NewGreedyIC
The key inefficiency of greedy is that in each iteration, marginal gains for all candidate nodes are re-
estimated from scratch using fresh Monte Carlo simulations. NewGreedy improves this by reusing the
same set of live-edge samples across all nodes simultaneously.

1. Generate R live-edge graphs at the beginning.

2. For each node u, record which nodes it can reach in each sampled graph.

3. When selecting seeds, the marginal gain of a candidate node is computed from these pre-recorded
reachability sets rather than re-running simulations.

This reduces complexity from O(k · n · R · m) to O(k · R · m), an O(n) factor improvement.
Pseudocode:

9
Algorithm 4 NewGreedyIC
0: Input: Graph G = (V, E), budget k, number of samples R
0: Generate R live-edge graphs {G′1 , . . . , G′R }
0: for each u ∈ V do
0: Compute Reach[u][r] = nodes reachable from u in G′r
0: end for
0: S←∅
0: for i = 1 to k do
0: For each u ∈ V \ S, compute marginal gain from Reach[u] (excluding already covered nodes)
0: Select u∗ with maximum gain
0: S ← S ∪ {u∗ }
0: end for
0: return S =0

4.2.3 MixedGreedy
MixedGreedy is a hybrid algorithm designed to balance initialization cost and incremental efficiency:

• The first round is performed using NewGreedy (reusing live-edge samples).

• Subsequent rounds use CELF’s lazy evaluation to avoid recomputation.

This reduces the overhead of CELF’s first iteration while retaining its benefits in later rounds.

4.2.4 DegreeDiscountIC
DegreeDiscount is a simple heuristic inspired by degree centrality. In influence maximization, the degree
of a node is a good proxy for influence, but once a neighbor is already selected as a seed, the marginal
contribution of the node decreases. DegreeDiscount adjusts a node’s degree to account for already
chosen neighbors:

DD(u) = du − 2tu − (du − tu )tu · p,

where:

• du = out-degree of node u,

• tu = number of neighbors of u already in the seed set,

• p = propagation probability (often uniform, e.g., 0.01).

Nodes are selected iteratively by maximum DD(u) until k seeds are chosen. Its complexity is
O(k log n + m), making it extremely fast.
Pseudocode:

10
Algorithm 5 DegreeDiscountIC
0: Input: Graph G = (V, E), budget k, propagation probability p
0: For each node u, set score[u] ← du , tu ← 0
0: S←∅
0: for i = 1 to k do
0: Select u∗ = arg maxu∈V \S score[u]
0: S ← S ∪ {u∗ }
0: for each neighbor v of u∗ do
0: tv ← tv + 1
0: Update score[v] ← dv − 2tv − (dv − tv )tv · p
0: end for
0: end for
0: return S =0

Implications for our framework:

• NewGreedyIC and MixedGreedy offer a balance of accuracy and speed — but require significant
memory to store reachability sets.

• DegreeDiscountIC is highly scalable, near-instantaneous, and achieves spreads within ≈ 3% of

greedy.

• In community subgraphs (smaller n), DegreeDiscountIC is particularly effective and practical.

4.2.5 Reverse Influence Sampling

Reverse Influence Sampling (RIS) reformulates influence maximization as a maximum coverage prob-
lem over sampled Reverse Reachable (RR) sets. An RR set for a node v is the set of nodes that can reach
v in a sampled live-edge graph. The algorithm samples a collection R of such RR sets and then selects
a seed set that covers the largest number of RR sets (maximum coverage).

Key steps:

1. Precomputation: Draw a (potentially large) number θ of RR sets before the seed-selection

step.
 The parameter θ is chosen to give probabilistic approximation guarantees; in theory θ =
(n+m)k log n
Θ ε2
. The cost of generating these RR sets is the major upfront expense.

2. Coverage and removal: During seed selection, when a seed node u is chosen, all RR sets con-
taining u are considered covered and removed from the remaining collection. This ensures that
subsequent selections maximize coverage over the uncovered sets.

11
Algorithm 6 Reverse Influence Sampling (RIS)
0: Input: Graph G = (V, E), seed budget k, error tolerance ε
0: Output: Seed set S
0: Compute θ based on (n, m, k, ε)
0: R←∅
0: for i = 1 to θ do
0: Sample a random node v uniformly from V
0: Generate a live-edge graph G′ under IC model
0: Compute RR-set R(v) = nodes that can reach v in G′
0: R ← R ∪ {R(v)}
0: end for
0: Initialize S ← ∅
0: for i = 1 to k do
0: Select node u that appears in the maximum number of uncovered RR sets
0: S ← S ∪ {u}
0: Remove all RR sets containing u from R
0: end for
0: return S =0

Pseudocode:

Complexity: The precomputation of θ RR sets is the dominant cost, with expected time O(θ·avg RR size).
The seed selection step is equivalent to solving a maximum coverage problem, typically implemented
using efficient data structures (e.g., heaps or hash maps).

Practical Implication for Community Decomposition: When communities are small (nc ≪ n), a
global θ tuned for the full graph may lead to heavy oversampling at the community level. The precom-
putation cost then dominates runtime, reducing practical gains. We recommend:
• Adapting θ per community proportional to |Vc | and |Ec |.
• Using fast heuristics (PageRank, DegreeDiscountIC) for small/medium communities.
• Reserving RIS for large communities above a chosen size/edge threshold.
This ensures that RIS remains efficient and competitive in hybrid community-based pipelines.

4.2.6 HITS (Revised explanation and caveats)

HITS computes two mutually reinforcing scores for each node: an authority score av and a hub score
hv . The update rules are: X X
av = hu , hv = au ,
(u,v)∈E (v,u)∈E

with normalization between iterations.

Kleinberg’s original use-case for HITS was query-centered web search: construct a small root set by
crawling pages returned for a query, expand it into a focused subgraph, then run HITS on that subgraph.
In this formulation HITS is inherently query-dependent because the selected root set changes per query.
In contrast, one can run HITS globally, but the interpretability of hub/authority scores for influence
propagation in social networks is weaker: HITS emphasizes link patterns that are characteristic of edi-
torial/curatorial structures rather than probabilistic diffusion processes. For these reasons HITS is best
kept as a conceptual baseline rather than a practical method for seed selection in our community-based
pipeline.

12
4.2.7 PageRank
Motivation PageRank, introduced by Brin and Page (1998), was originally designed for ranking web
pages but has since become a fundamental centrality measure in networks. It models a random walk
with restarts: a random surfer at node u either (1) follows an outgoing edge with probability d (the
damping factor), or (2) teleports uniformly to any node with probability 1 − d. This stochastic process
converges to a stationary distribution that reflects the relative influence of nodes. In the context of
influence maximization, PageRank is attractive because it approximates how activation can flow along
edges in a diffusion process, while being far more scalable than greedy or sampling-based methods.

Mathematical Formulation The PageRank score of a node v is defined recursively as:

1−d X P R(u)
P R(v) = +d ,
n deg + (u)
(u,v)∈E

where d ∈ (0, 1) is the damping factor (typically d = 0.85), deg + (u) is the out-degree of u, and n = |V |
is the total number of nodes. In matrix form, PageRank corresponds to finding the principal eigenvector
of the Google matrix M = dP + (1 − d) n1 11T , where P is the row-normalized adjacency matrix.

Algorithm A practical computation uses power iteration until convergence:

Algorithm 7 PageRank
0: Input: G = (V, E), damping factor d, max iterations T , tolerance ε
0: Output: PageRank scores P R
0: n ← |V |; initialize P R[v] ← 1/n for all v ∈ V
0: for iter = 1 to T do
0: newP R[v] ← (1 − d)/n for all v ∈ V
0: for each edge (u, v) ∈ E do
0: newP R[v] ← newP R[v] + d · P R[u]/outdeg(u)
0: end for
0: if ||newP R − P R||1 < ε then
0: break
0: end if
0: P R ← newP R
0: end for
0: return P R =0

Convergence and Complexity Power iteration converges in T = O(log(1/ε)/(1−d)) steps in theory,

but in practice convergence is typically reached within 30–50 iterations for ε ≈ 10−6 and d = 0.85.
Each iteration costs O(m), where m = |E| is the number of edges, giving total complexity O(T · m).
This makes PageRank highly scalable, and suitable even for million-scale networks. It can also be
parallelized easily across edges.

Context in Our Framework PageRank is especially effective in our community-based strategy:

• Within each community subgraph, it quickly ranks nodes by influence potential without expensive
Monte Carlo simulations.
• The scores correlate strongly with greedy influence spread (as confirmed in Experiment 1).
• Its runtime is orders of magnitude faster (seconds vs. hours), enabling large-scale feasibility.
Thus, PageRank emerges as the most practical heuristic baseline in our pipeline, balancing scalability,
accuracy, and theoretical grounding.

13
4.3 Experimental Setup
Dataset: We conduct our experiments on the DBLP collaboration network, a large-scale benchmark
graph widely used in network science. It consists of publication relationships among authors.

• Nodes: ∼3 million authors

• Edges: ∼10 million citation/co-authorship links
• Graph type: undirected, unweighted

Community detection: We applied Infomap to partition DBLP into communities:

• ∼20,000 total communities
• Average size ≈ 149 nodes
• Largest community ≈ 1400 nodes
The distribution of community sizes is highly skewed: most communities are very small, while a few
large ones dominate the network. This heavy-tailed structure is consistent with real-world collaboration
networks.

Figure 1: Community size distribution in DBLP after Infomap partitioning. The distribution is heavy-
tailed: many small groups, few large clusters.

Diffusion Model and Estimation.

• Diffusion: Independent Cascade (IC) model
• Influence estimation: Monte Carlo simulations via live-edge graph sampling
• Evaluation domain: Experiments are run separately on the induced subgraph of each community.

Community Hypergraph Construction and Use:

• Motivation: While community detection reduces complexity by allowing local seed selection, we
also need a higher-level representation to analyze how influence flows between communities. For
this purpose, we construct a community hypergraph, where nodes represent communities rather
than individual vertices.

14
Construction.
• Communities {C1 , C2 , . . . , Cm } are obtained using Infomap.
• For each community Ci , we select its top-k influential nodes (e.g., by PageRank).
• Using diffusion simulations (IC model), we estimate how many nodes in each other community
Cj become influenced by these seeds.
• We then add a directed edge Ci → Cj with weight equal to this expected influence spread. A
self-loop Ci → Ci captures internal influence.

Figure 2: Community hypergraph H constructed from Infomap communities. Each node represents a
community, edges represent inter-community influence, and self-loops capture intra-community rein-
forcement.

Interpretation. The resulting hypergraph H is a coarse-grained influence network:

• Edge weights quantify inter-community influence channels.
• Self-loops capture intra-community reinforcement.
• The graph allows us to reason about propagation at the community level rather than individual
nodes.

Planned Uses. This hypergraph opens up several directions for experimentation:

• Seed allocation strategies:
1. Pick top influencer from each community (uniform allocation).
2. Allocate seeds proportional to community size.
3. Focus on boundary communities with high outgoing edge weights.
4. Hybrid schemes combining intra-community and cross-community considerations.
• Influence flow analysis: Study how total spread varies with different allocation strategies and
quantify the fraction of influence flowing within vs. across communities.
• Scalability: The hypergraph is much smaller than the original network, enabling rapid prototyp-
ing of allocation heuristics before validation on the full graph.

15
Placement in our framework. We treat the community hypergraph as a mesoscopic representation:
it sits between the micro-level (individual nodes) and the macro-level (the whole network). This repre-
sentation is already used in Experiment 2 and will serve as the foundation for future experiments in seed
allocation and comparative studies.

4.3.1 Experiment 1: PageRank vs Greedy Influence Spread

Setup:
1. Run Infomap on the input graph G to obtain community partitions {C1 , C2 , . . . , Cm }.

2. For each community Ci :

• Compute PageRank scores restricted to the subgraph induced by Ci .

• Select the top-k nodes by PageRank score.
• Separately, run the greedy influence maximization algorithm under the IC model:
(a) Estimate node influence using Monte Carlo live-edge sampling.
(b) Iteratively add the node with the maximum marginal gain until k seeds are selected.

3. For each Ci , compare the PageRank-selected set with the greedy-selected set:

• Compute overlap between the two top-k sets.

• Compare expected influence spread from each seed set (again via Monte Carlo sampling).
• Record runtime for PageRank vs greedy simulation.

Metric for comparison:

• Set overlap ratio: |SPR ∩ SGreedy |/k.

• Influence spread difference: σ(SPR ) vs. σ(SGreedy ).

• Runtime comparison: seconds required to compute PageRank vs. greedy selection.

4.3.2 Experiment 2: Evaluate whether high PageRank nodes from a community are highly in-
fluential within that community or outside of it
Setup:
1. For each community Ci , extract the top-k PageRank nodes (within the subgraph induced by Ci ).

2. For each such node, estimate its influence spread under the IC model (via live-edge sampling) and
record which nodes across the full graph are activated in each sampled run.

3. Aggregate the per-node influence by mapping influenced nodes to their communities to produce
directed weighted edges in a community hypergraph H: an edge Ci → Cj has weight equal to
the expected number of nodes in Cj influenced by the top-k PageRank nodes of Ci . The self-loop
Ci → Ci captures intra-community influence.

Metric 1: Normalized intra-share ratio.

Influence within Ci
|Ci |
Ratioi = Influence within Ci outside Ci
.
|Ci | + Influence
|V |−|Ci |

This metric represents the fraction of normalized influence retained inside Ci (values in [0, 1]). Values
close to 1 indicate that, after normalizing by community sizes, most influence from Ci ’s top nodes
remains inside Ci .

16
Metric 2: Distribution of average spread for the topk pageranknodesineachcommunity. In ad-
dition, we compute the average influence of the top-k PageRank nodes on a per-community basis:

• Within-community: average influenced nodes per seed divided by |Ci |.

• Outside-community: average influenced nodes per seed divided by |V | − |Ci |.

4.4 Experimental Results

4.4.1 Experiment 1: PageRank vs Greedy Influence Spread

Figure 3: Comparison of influence spread from Top-k nodes selected by PageRank vs. Greedy.

• Top-k Comparison: We found strong overlap between the top-k nodes from PageRank and those
from IC-based greedy selection, often exceeding 70–80% for k = 10.

• Spread Performance: The influence spread achieved by PageRank-selected seeds was within
5–10% of the spread from greedy selections.

• Scalability Gains: PageRank computation was orders of magnitude faster than influence spread
estimation via Monte Carlo, providing a dramatic speedup with comparable accuracy.

• Conclusion: PageRank is a scalable and effective heuristic for identifying influential nodes
within communities.

17
4.4.2 Experiment 2: Intra vs Inter-Community Influence

Figure 4: Distribution of average spread within compared to total spread of top k pagerank nodes.

Figure 5: Distribution of average spread for the top k pagerank nodes in each community.

• Internal vs External Influence: Across all tested communities, we observed Ratioi values consis-
tently biased towards the higher end (closer to 1), showing that a disproportionately large fraction
of normalized influence spread remains inside the originating community. While inter-community
influence edges are present, their normalized weight is significantly smaller compared to self-
loops.

• avg spread for top k nodes of a community within and out Within-community normalized
spreads are one to two orders of magnitude larger than outside-community spreads. Most seeds
have meaningful impact only inside their communities.

• Conclusion: These results suggest that communities behave as semi-autonomous propagation

units: seeds exert stronger influence inside their own communities than across boundaries. This
observation supports the use of community decomposition for influence maximization, though it
does not imply communities are fully isolated — cross-community edges still provide secondary
propagation pathways.

18
4.5 Lessons Learned
1. Community Decomposition is Effective: Partitioning the graph using Infomap significantly re-
duced computational burden and revealed structural boundaries of influence.
2. Influence Estimation is Tractable with Sampling: The live-edge graph formulation is effective
but remains expensive, reinforcing the need for scalable heuristics.
3. Greedy and CELF are Benchmarks, Not Solutions: These algorithms are too slow for practical
deployment, even on community-sized subgraphs.
4. NewGreedy, MixedGreedy, and DegreeDiscount Bridge the Gap: These methods offer sub-
stantial efficiency gains, with DegreeDiscountIC being a highly effective heuristic.
5. RIS Provides Scalability, but at a Cost: RIS is less compelling in a community-based framework
where graphs are already smaller and practical inefficiencies can arise.
6. PageRank is a Strong Practical Heuristic: Empirical results confirmed PageRank as a core
algorithm in our framework, offering an excellent balance of scalability and accuracy.

5 Future Plan for This Semester

Building upon our progress, the next stage aims to consolidate our scalable framework for influence
maximization by rigorously validating our hypothesis and refining seed selection strategies.

5.1 Refining Seed Allocation among Communities

Having established that our central hypothesis holds, the next challenge is to determine how to optimally
allocate seeds within communities. We plan to explore several heuristic strategies:
• Top-Influence Heuristic: Selecting the single most influential node in each community.
• Proportional Allocation: Allocating more seeds to larger communities to ensure coverage is
proportional to community size.
• Boundary Node Sensitivity: Isolate boundary nodes to evaluate if heuristics overemphasize
them, potentially undermining the hypothesis.

5.2 Comparative Evaluation Across Algorithms

We will conduct a systematic comparison of all studied algorithms (Greedy, CELF, NewGreedy, Mixed-
Greedy, DegreeDiscount, RIS, HITS, PageRank).
• Metrics: Influence spread, runtime, memory usage, and the intra/inter-community ratio.
• Datasets: Extend to include large benchmark datasets (e.g., NetHEPT, Epinions).
• Scalability Tests: Run experiments on progressively larger networks to quantify computational
savings.

5.3 Scalability Enhancements and Implementation

To ensure practical feasibility:
• Variable Community Sizes: Extend the algorithm to handle non-uniform community sizes.
• Parallelization: Implement Monte Carlo simulations and PageRank using multi-threading.
• Memory Efficiency: Investigate sparse data structures to manage large graphs.

19
5.4 Deliverables
By the end of the semester, we aim to produce:

1. A validated community-based framework for scalable influence maximization.

2. A comparative performance study of classical, heuristic, and RIS-based algorithms.

3. A scalable community-constrained PageRank algorithm with intra-community guarantees.

4. A complete, detailed report and presentation documenting methodology, results, and analysis.

20
6 PageRank-Based Seed Selection Strategies
PageRank-based strategies offer an attractive middle ground between purely centrality-based heuristics
and computationally heavy greedy algorithms. Because PageRank captures global structural importance
while remaining scalable on large graphs, several variants have been proposed to better align PageRank
scores with diffusion behavior under the Independent Cascade (IC) model. We summarize three such
methods—PRTH, PRDD, and HPR-Greedy—including their intuition, algorithmic components, and
validated results from the literature.

6.1 PRTH — PageRank with Propagation Probability Threshold (SEKE’21)

Intuition
Standard PageRank tends to overemphasize nodes connected to many low-quality neighbors (e.g., nodes
surrounded by degree-1 “leaf” nodes). Such nodes receive high PageRank but contribute little to IC-
based diffusion. PRTH corrects this by pruning edges unlikely to support information propagation,
using a weight derived from the relative PageRank values of incident nodes. This removes peripheral
and weak-signal edges, leaving a structurally meaningful backbone on which PageRank is recomputed.
The intuition aligns with diffusion behavior: strong propagation occurs along edges connecting
structurally important nodes, and edge-pruning forces PageRank to focus on these diffusion-relevant
pathways.

Algorithm (PRTH)

Algorithm 8 PRTH(G, k)
1: Compute PageRank PR(v) for all v ∈ V .
2: for each edge (u, v) ∈ E do
PR(u)
3: wu→v = PR(u)+PR(v)
PR(v)
4: wv→u = PR(u)+PR(v)
5: Assign edge weight w(u, v) = max(wu→v , wv→u )
6: end for
1 P
7: Compute threshold th = |E| e∈E w(e).
8: Remove all edges with weight < th, yielding pruned graph G′ .
9: Recompute PageRank PR′ on G′ .
10: return the top-k nodes as seeds. =0

Summary of Results (From SEKE’21)

• PRTH improves influence spread over Degree, DegreeDiscount, and standard PageRank.

• On dense graphs (e.g., Facebook, NetPHY), PRTH achieves spread close to RIS while running
much faster.

• Provides 20–40% improvement over vanilla PageRank across multiple datasets.

• Computational cost is only slightly above PageRank, far below greedy and RIS.

21
6.2 PRDD — Hybrid of PRTH and DegreeDiscount (SEKE’21)
Intuition
Although PRTH improves diffusion awareness, it still tends to select seeds clustered within dense re-
gions (seed aggregation), reducing coverage. PRDD counteracts this by combining PRTH scores with
DegreeDiscount, which penalizes selecting multiple seeds from tightly knit neighborhoods. This pro-
duces a balance between (i) structural influence (via PRTH) and (ii) diversity (via local degree discount).
The idea: high-PageRank seeds are strong influencers, but diversity is necessary to avoid re-
dundant spread.

Algorithm (PRDD)
Combined Score:
P RT H(v) DD(v)
P D(v) = (1 − α) +α ,
max P RT H max DD
where 0.1 ≤ α ≤ 0.3 (empirically validated).
Procedure:

1. Compute PRTH scores.

2. Initialize DegreeDiscount for all nodes.

3. Normalize both scores and compute P D(v).

4. Iteratively select the node with highest P D(·).

5. Update DegreeDiscount for its neighbors and recompute their combined scores.

6. Return the top-k nodes.

Summary of Results (From SEKE’21)

• PRDD achieves the highest diffusion among all centrality-based heuristics tested.

• Outperforms PRTH by 10–15%, especially on sparse and medium-density networks.

• Produces significantly better seed diversity than PRTH alone.

• Runtime is slightly above PRTH but still dramatically faster than RIS and greedy methods.

6.3 HPR-Greedy — High-PageRank Candidate Filtering + Greedy Refinement

Intuition
Pure PageRank lacks marginal-gain awareness, while greedy methods are expensive on large graphs.
HPR-Greedy bridges this gap by:
[label=(3)]

1. Using PageRank to generate a high-quality but compact candidate set,

2. Running greedy only on those candidates, drastically reducing evaluation cost.

This leverages the empirical observation (validated in IM literature) that PageRank surfaces struc-
turally influential nodes with high likelihood of participating in large cascades, making the candi-
date space both meaningful and manageable.

22
Algorithm (HPR-Greedy)
Inputs: Graph (G), seed budget (k) Steps:

1. Compute PageRank for all nodes.

2. Select top-m PageRank nodes (typically m ≪ |V |).

3. Run Kempe-style greedy IM restricted to these m candidates.

4. Return the greedy-selected k seeds.

Summary of Observed Performance (Across Prior Literature)

• Achieves near-greedy influence spread, often within 5–10% of full greedy.

• Reduces greedy runtime by orders of magnitude (candidate set ≪ full graph).

• Performs substantially better than pure PageRank because marginal gain prevents redundant seed
selection.

• Particularly effective in modular graphs (e.g., DBLP) where PageRank identifies good inter-
community connectors.

6.4 Summary
Together, PRTH, PRDD, and HPR-Greedy illustrate a progression of increasingly diffusion-aware PageRank-
based strategies:

• PRTH improves PageRank by pruning weak edges aligned with IC diffusion.

• PRDD further enhances performance by incorporating diversity through DegreeDiscount.

• HPR-Greedy retains PageRank’s scalability while recovering greedy-level accuracy through can-
didate filtering.

These PageRank-based approaches provide scalable, structurally informed alternatives to full

greedy IM, and the empirical results in the SEKE’21 paper confirm that PageRank variants can signifi-
cantly bridge the gap between classical centrality heuristics and more expensive greedy algorithms.

7 Fine-Tuning the Diffusion Probability (p) in the Independent Cascade

Model
In our IC implementation, each directed edge is retained with probability (p) to form a sampled live-
edge graph. A node’s influence in one sample equals the size of the connected component containing it.
Therefore, the component-size distribution induced by (p) determines whether influence measurements
remain meaningful for community-based analysis.

7.1 Component Size Distributions Across (p)

We examined four values of (p): (0.01), (0.03), (0.05), and (0.07). The resulting component-size distri-
butions are shown in the following figures:

23
(a) Component Size Distribution (log–log), (p = 0.01) (b) Component Size Distribution (log–log), (p = 0.03)

(c) Component Size Distribution (log–log), (p = 0.05) (d) Component Size Distribution (log–log), (p = 0.07)

Figure 6: Component Size Distribution (log–log) for various values of p.

The percentage of precomputed PageRank nodes (20,000 PG-nodes) falling into the largest compo-
nent is shown in Figure 13, and summarized quantitatively below:

Figure 7: Percentage of PG-nodes in Largest Component vs (p)

Quantitatively, we observe the following concentration of influential nodes:

p 0.01 0.03 0.05 0.07
PG-nodes in largest comp 0.00% 0.02% 3.49% 21.76%
Summary of structural behavior:

• (p = 0.01): Extremely fragmented; components mostly size 1–10.

• (p = 0.03): Heavier tail emerges, but diffusion remains limited.

• (p = 0.05): Balanced heavy-tailed structure with one moderate large component and many mid-
sized ones.

• (p = 0.07): Clear percolation threshold; a giant component dominates the graph.

24
7.2 Choosing (p = 0.05)
A suitable (p) must avoid both extremes:
1. Too small (p) → overly fragmented graphs, trivial influence values.
2. Too large (p) → a giant component that absorbs influential nodes and destroys community reso-
lution.
The sharp jump in PG-node concentration from 3.49% at (p = 0.05) to 21.76% at (p = 0.07)
indicates a percolation transition. Thus, (p = 0.05) lies in the stable region where diffusion is meaningful
but not dominated by a single giant component.

7.3 Implications for Our Pipeline

The selection of (p = 0.05) ensures the following properties are maintained for effective influence
maximization:
• Influence (component-size) varies meaningfully across nodes.
• PG-nodes remain well distributed across components, preserving community-level differences.
• Diffusion is neither trivial (as in (p = 0.01)) nor monolithic (as in (p = 0.07)).
Accordingly, (p = 0.05) strikes the optimal balance between diffusion realism and structural hetero-
geneity, and is the value adopted for all subsequent experiments.

8 Experiment 1: Greedy vs. PageRank Seed Selection

8.1 Difference from the Previous Experiment
In the earlier experiment, our goal was to validate whether PageRank can identify nodes with similar
individual influence as greedy. That is, we compared:
• the marginal influence of the top-k Greedy nodes, and
• the marginal influence of the top-k PageRank nodes
This earlier evaluation was node-centric: We asked, “Is the k-th PageRank node as influential as the
k-th greedy node?”

How the Current Experiment Differs

In this experiment, we shift from node-level to seed set–level comparison.
1. We compare cumulative influence spread of the first k seeds selected by:
• Greedy (Kempe’s algorithm), and
• Naı̈ve Top-k PageRank nodes
2. We perform the comparison in two ways:
• Global Average (across all communities)
• Within the Two Most Influential Communities
This experiment is seed-set focused, answering the question:
“If we select the first k nodes using PageRank instead of greedy, how much influence do we
lose?”
This is a more realistic question for scalable IM, since the final objective is not to match the influence of
individual nodes, but to choose seed sets effectively.

25
8.2 Global Comparison: Greedy vs. PageRank Across All Communities

Figure 8: Greedy vs. PageRank – Average Cumulative Influence Spread Across All Communities

To assess how naı̈ve PageRank compares with greedy selection at a broader scale, we evaluated the
average cumulative influence spread obtained by the top-k seeds across all communities, shown in
Figure X. The results exhibit a clear and consistent pattern: while both methods show steadily increasing
spread as k grows, the greedy algorithm maintains a uniformly higher influence spread for all values of
k, and the gap widens progressively.
For very small seed sets (k = 1 or k = 2), the performance of the two methods is nearly identical.
This reflects the fact that both PageRank and greedy tend to identify the same highly central individuals
as the first seeds. However, as soon as k increases beyond this regime, the curves diverge. PageR-
ank continues to select nodes that are structurally important but often clustered in dense regions with
substantial neighborhood overlap. Because PageRank does not account for marginal gain, many later
selections contribute redundant influence.
In contrast, the greedy method explicitly evaluates marginal spread at each iteration, thereby avoid-
ing overlap and consistently expanding coverage into new portions of the graph. This divergence be-
tween the methods, which becomes more pronounced as k grows, is fully aligned with theoretical expec-
tations under submodularity: PageRank serves as a useful but incomplete surrogate for influence-based
ranking, whereas greedy continues to optimize true marginal contributions.
Overall, this global comparison confirms that PageRank is competitive for the earliest seeds but
becomes progressively less effective as the seed budget grows, reinforcing the necessity of marginal-
gain reasoning when selecting multiple seeds even within community-level settings.

8.3 Community-Level Comparison (Top Two Communities)

To further understand the gap between greedy and naı̈ve PageRank selection at the community level,
we examined the two communities with the highest overall influence under greedy selection. The
results, shown in Figure Y, reveal a consistent pattern across both communities. In each case, greedy
achieves a substantially higher cumulative spread than PageRank, and this gap widens as k increases.

26
 Figure 9: Within-Community Comparison of Greedy vs. PageRank for the Top Two Communities

PageRank typically provides a strong first seed but saturates quickly, indicating that subsequent PageRank-
ranked nodes lie in densely interconnected subregions whose influence neighborhoods significantly over-
lap. Greedy, in contrast, continues to add nodes that expand coverage into previously unreached parts of
the community.
Across both communities, PageRank plateaus early—around 200 spread in the larger community
and around 90 in the smaller one—whereas greedy continues to grow well beyond these levels. This
demonstrates that even within a single community, PageRank’s ranking by structural importance does
not necessarily reflect marginal influence potential. Greedy’s advantage becomes particularly clear in
smaller or moderately dense communities, where redundancy among PageRank-selected nodes causes
rapid saturation.
Overall, these results show that the difference between greedy and naı̈ve PageRank can be significant
even at the intra-community level, reinforcing the importance of marginal-gain reasoning when selecting
multiple seeds within the same community.

8.4 Conclusions from Experiment 1

Key Takeaways
1. Greedy achieves significantly higher cumulative influence spread than PageRank, both glob-
ally and within individual communities.

2. PageRank performs reasonably well for the first few seeds, but quickly saturates due to redun-
dant selections.

3. Within communities, PageRank:

• Prefers structurally central nodes,

• But fails to diversify selections,
• Leading to diminishing marginal returns.

4. Greedy:

• Exploits community structure more effectively,

• Selects nodes reaching previously uncovered regions,
• Maintains consistent marginal gains.

27
Why This Matters for Our Work
• The results confirm that naı̈ve PageRank is not a drop-in replacement for greedy.

• However, PageRank remains valuable as a first-stage filter:

– Very fast to compute

– Identifies promising candidates
– Can be refined using improved strategies (HPR-Greedy, PRTH/PRDD, community-based
pruning)

This experiment establishes the baseline performance of PageRank versus greedy and justifies the need
for hybrid, community-aware, or diffusion-aware PageRank enhancements for scalability.

9 Experiment 2 — Global Benchmarking of Seed Selection Strategies on

the DBLP Network
This experiment evaluates the global performance of multiple seed selection strategies on the DBLP
collaboration network, which contains approximately 3 million nodes and 10 million edges. The ob-
jective is to assess how classical greedy optimization, centrality-based heuristics, and community-aware
approaches perform in network-wide influence maximization under the Independent Cascade (IC)
model for a seed-set size of k = 50. This complements the within-community analysis of Experiment 1
by shifting focus to global diffusion behavior.

Figure 10: Cumulative influence spread of top-k seeds (k ≤ 50) across all methods.

9.1 Seed Selection Strategies

Five methods were implemented to systematically examine how centrality, community structure, and
greedy refinement affect influence spread at scale.

28
9.1.1 Full Greedy (GRE)
The classical Kempe et al. greedy algorithm executed over the entire DBLP network. At each iteration,
the node with the highest marginal increase in IC spread is selected. This method serves as the upper
bound on achievable influence but is computationally prohibitive at this graph scale.

9.1.2 Community-Based High-Degree (DEG)

Using the Infomap communities (≈ 20, 000 total), communities were sorted by size and the top 50
communities were selected. Within each of these communities, the highest-degree node was chosen as
a seed. This method enforces community diversity while relying on degree centrality to identify locally
influential nodes.

9.1.3 Global High-Degree (DEG GLOBAL)

This strategy selects the top 50 nodes by global degree across the entire DBLP graph. Degree is a
fast and intuitive heuristic, but global high-degree ranking often concentrates heavily on dense research
subfields, leading to considerable overlap in the neighborhoods influenced by selected nodes.

9.1.4 Community-Based PageRank (PG)

Using the same top-50 communities as above, the top PageRank node from each community was
chosen. PageRank captures structural importance derived from random-walk dynamics and highlights
nodes with broad intra-community connectivity.

9.1.5 Greedy over PageRank Candidates (GREEDY PAGERANK)

For scalability, the top 10 PageRank nodes were extracted from each of the top 1000 communities,
producing a reduced candidate set of roughly 10,000 nodes. The greedy algorithm was executed only
on these candidates, significantly reducing computational cost while maintaining access to structurally
influential nodes across the community landscape.

9.2 Results
The cumulative spread curves for all strategies demonstrate a clear hierarchy of performance. Approxi-
mate influence spread at k = 50 is:

• GRE ≈ 42, 000

• GREEDY PAGERANK ≈ 36, 000

• PG ≈ 25, 000

• DEG GLOBAL ≈ 24, 500

• DEG ≈ 19, 500

The results reveal strong separation between greedy-based approaches and pure centrality-based
heuristics.

29
9.3 Analysis and Interpretation
The full greedy algorithm (GRE) achieves the highest influence spread by explicitly accounting for
marginal gain at each iteration. In a network such as DBLP—characterized by dense local structures,
overlapping neighborhoods, and modular research communities—greedy excels because it avoids re-
dundant selections and progressively expands coverage across distinct influence regions.
The performance of GREEDY PAGERANK provides key insight into scalability. Although PageR-
ank emphasizes structurally significant nodes, the greedy refinement step eliminates redundancy by eval-
uating marginal gain over the filtered candidate set. As a result, GREEDY PAGERANK attains near-
greedy performance while operating on less than 0.5% of the nodes, demonstrating the effectiveness
of combining community filtering with structural ranking.
A striking observation is the near coincidence of PG and DEG curves. Within large communities,
PageRank and degree centrality are strongly correlated in DBLP due to dense internal collaboration
patterns: prolific authors tend to have both high degree and high PageRank. Thus, selecting one seed
per community using either metric yields comparable influence, with both strategies capturing locally
prominent nodes but failing to adapt to global redundancy or cross-community connectivity.
In contrast, DEG GLOBAL performs substantially worse than PG and DEG. Global high-degree
ranking concentrates heavily in a few extremely dense subfields. Selecting the top 50 degree nodes
leads to highly redundant seeds—most of their influence regions overlap significantly, producing rapid
saturation and poor marginal gains. Moreover, this strategy neglects seeds from smaller but well-
positioned communities that could extend diffusion into new parts of the network. This explains why
DEG GLOBAL attains the lowest spread among the heuristics.
Collectively, these observations reinforce a key principle: Effective global influence maximization
in large, community-structured networks requires balancing structural prominence with coverage
across diverse regions of the graph.

• Centrality-only methods overlook marginal redundancy.

• Pure community diversity ignores the heterogeneous influence potential of communities.

• Hybrid approaches with structural filtering and greedy refinement (e.g., GREEDY PAGERANK)
offer the best balance between scalability and influence quality.

9.4 Conclusion
This experiment demonstrates that scalable influence maximization benefits from combining commu-
nity structure and structural centrality with marginal-gain awareness. Full greedy yields the high-
est spread but is infeasible at this scale. GREEDY PAGERANK emerges as a powerful alternative—
retaining near-greedy influence while drastically reducing computational overhead. Community-based
selection (PG, DEG) offers stable but limited performance, and global degree (DEG GLOBAL) suf-
fers heavily from redundancy. These findings motivate the design of scalable influence maximization
pipelines that integrate community filtering and structural centrality with lightweight greedy refinement.

10 Related Community-Based Influence Maximization Frameworks

Community-aware approaches provide a scalable way to approximate influence maximization on large
networks by isolating computation within smaller, densely connected subgraphs and coordinating selec-
tion across communities. We summarize two representative frameworks— CoFIM and the ILP-based
Community-Aware Influence Maximization framework—highlighting their core mathematical ideas
and selection procedures.

30
10.1 CoFIM: A Community-Based Submodular Surrogate for Scalable Influence Max-
imization
(Shang et al., KBS 2017)
CoFIM (Community-based Influence Maximization) proposes a principled surrogate objective that
approximates the Independent Cascade (IC) influence function by combining neighborhood expansion
and community activation. Instead of relying on computationally expensive Monte-Carlo simulations,
CoFIM leverages the structural decomposition of large social networks into well-defined communities
and models influence diffusion as a two-level process:
1. Seed nodes reach cross-community neighbors through their immediate and second-order connec-
tivity.

2. Activated neighbors propagate influence internally within their respective communities.

By separating these two types of influence effects, CoFIM constructs a surrogate function that is mono-
tone, submodular, and computationally inexpensive, enabling scalable greedy optimization on very large
graphs.

Mathematical Formulation and Submodularity of CoFIM

CoFIM’s surrogate objective is constructed by combining two set functions: a neighborhood-expansion
term capturing cross-community reach and a community-activation term capturing breadth of com-
munity coverage.
Given a seed set S, let:
• N (S): union of first- and second-order neighbors (N1 ∪ N2 ) of nodes in S.

• Γ(S): set of communities touched by N (S).

The surrogate influence function is:

F (S) = |N (S)| + γ · |Γ(S)|,

where γ > 0 is a community-weight parameter. CoFIM proves that each component is submodular, and
therefore the sum is submodular.

Submodularity of the Neighborhood Expansion

S Term (f1 (S) = |N (S)|) The term f1 (S) represents
a set union operation over S: N (S) = v∈S N (v). For submodularity (f1 (A ∪ {x}) − f1 (A) ≥
f1 (B ∪ {x}) − f1 (B) for A ⊆ B), the argument is based on set difference:

|N (A ∪ {x})| − |N (A)| = |N (x) \ N (A)|

Since N (A) ⊆ N (B) =⇒ N (x) \ N (A) ⊇ N (x) \ N (B)
|N (x) \ N (A)| ≥ |N (x) \ N (B)|
=⇒ |N (A ∪ {x})| − |N (A)| ≥ |N (B ∪ {x})| − |N (B)|

The marginal gain from adding x diminishes as the seed set grows, proving that f1 is submodular.

Submodularity of the Community Activation Term (f2 (S) = |Γ(S)|) The community S set Γ(S) is
also expressed as a union of community contributions from each seed node: Γ(S) = v∈S Γ({v}). The
same set-union argument applies: a smaller set A touches fewer communities than B, so adding x to A
may activate more *previously unseen* communities than adding it to B. Thus, f2 is also submodular.
Since F (S) is the sum of two monotone submodular functions, it is itself submodular and mono-
tone. This allows the greedy algorithm to be applied, yielding the classical (1 − 1/e) approximation
guarantee without requiring Monte-Carlo simulations.

31
Intuition Behind the CoFIM Surrogate
CoFIM’s design is grounded in a structural observation: cross-community influence primarily arises
from highly connected nodes that serve as ”portals” between communities, not from peripheral nodes.

• Community boundaries limit diffusion: Edges crossing communities are few and often asso-
ciated with structurally strong individuals (connectors). Peripheral nodes have negligible cross-
community reach.

• Connectors matter: Nodes with high degree or high connectivity are most likely to maintain
cross-community ties and dominate influence propagation.

• 1-hop and 2-hop neighborhoods capture connectors: Most cross-community bridges appear in
1-hop (direct) or 2-hop (collaborators-of-collaborators) neighborhoods. Nodes beyond 2 hops are
deemed too distant structurally.

By examining only N ({v}) = N1 (v) ∪ N2 (v), CoFIM dramatically reduces computation while captur-
ing the critical structural pathways for cross-community influence.

CoFIM Procedure
1. Detect communities in the input graph.

2. For each node, precompute its local neighborhood N ({v}) coverage and the community set
Γ({v}) it potentially activates.

3. Apply a greedy algorithm using F (S) as the objective, incrementally updating the combined
neighborhood and community sets.

Performance Characteristics
Scalability Because marginal-gain evaluation depends only on precomputed 1-hop/2-hop neighbor-
hoods and community labels, it is extremely fast and the method scales almost linearly with graph size.
Experiments reported show 100 × –500× speedups compared to CELF/CELF++, making it suitable
for graphs with millions of nodes.

Influence Spread Despite its simplicity, CoFIM achieves influence spread much higher than centrality
baselines (degree, PageRank) and comparable to CELF/CELF++ greedy results, but with orders-of-
magnitude lower computation. This demonstrates that community-level structural features effectively
capture much of the behavior of full IC diffusion.

10.2 ILP-Based Community-Aware Influence Maximization

(2022 Community-Aware Framework)
In contrast to CoFIM’s global surrogate, this framework decomposes the influence maximization
process into two distinct stages:

1. Local Greedy Optimization Within Each Community For each community Ci , a full greedy
algorithm (CELF++) is applied to compute the top-k seeds based on the true influence function restricted
to that community:

Si = {Si,1 , Si,2 , . . . , Si,k }, Σi = {σi (Si,1 ), σi (Si,2 ), . . . , σi (Si,k )}.

Here, σi (·) is the influence spread measured within community Ci .

32
2. Progressive Budgeting Across Communities Instead of naively picking one seed per community
or allocating proportional budgets, the framework proposes a progressive budgeting algorithm that
selects communities based on marginal gains of their next-best local seed. This ensures that communities
with higher incremental influence contributions receive more seeds.

Progressive Budgeting Algorithm

Algorithm 9 Progressive-Budgeting
Require: S = {Si,j }, precomputed local seed sets for all communities Ci .
Require: Σ = {σi (Si,j )}, precomputed local influence spreads.
Require: Total budget k.
Ensure: Final seed set S ∗ .
1: for each community Ci do
2: Initialize local seed set Si = {Si,1 , . . . , Si,k }
3: Initialize local spreads Σi = {σi (Si,1 ), . . . , σi (Si,k )}
4: Initialize marginal gain δi = σi (Si,1 )
5: Initialize allocated budget bi = 0
6: end for
7: S ∗ = ∅
8: for l = 1 to k do
9: m = arg maxi δi {Community with maximum marginal gain}
10: bm = bm + 1 {Allocate a seed to community Cm }
11: S ∗ = S ∗ ∪ {Sm,bm } {Add its next best seed}
12: δm = σm (Sm,bm +1 ) − σm (Sm,bm ) {Update marginal gain}
13: end for
14: return S ∗ =0

Intuition
This algorithm treats each community as an independent “competitor” for budget, where the next best
local seed from each community is evaluated based on its marginal gain. Instead of fixing community
budgets beforehand, the allocation emerges dynamically, ensuring that communities contributing higher
incremental influence receive proportionally more seeds.

Performance Characteristics
Scalability Because CELF++ is executed only within communities—each much smaller than the full
graph—the local optimization phase is significantly faster than global greedy. The global budgeting
step adds only a lightweight comparison of precomputed marginal gains. Overall, the method reduces
runtime by an order of magnitude and scales efficiently with the number of communities.

Influence Spread Despite its reduced computational cost, the framework achieves influence spread
very close to full greedy. Progressive budgeting ensures seeds are allocated to communities with gen-
uinely high marginal impact, producing results within 5%–10% of global greedy while running far faster.

Summary
Both CoFIM and the ILP-based community-aware IM framework highlight complementary strategies
for leveraging community structure:

33
 • CoFIM replaces the global IC spread with a simple submodular surrogate defined through com-
munity activation.
• The ILP framework retains true greedy optimization but restricts it to communities first, followed
by a principled global budgeting step.

Together, these works demonstrate that communities provide meaningful structural units for scalable
influence maximization, motivating our exploration of PageRank-based community filtering, community-
pruned candidate sets, and hybrid greedy approaches.

Future Work
The present study demonstrates the effectiveness of PageRank-based community filtering and reduced
candidate sets for scalable influence maximization on large networks. Several promising research direc-
tions emerge from our findings and from recent community-aware IM frameworks.

a. Community Hypergraph–Driven Candidate Community Selection

We plan to construct and exploit a community hypergraph, where each node represents a commu-
nity detected in the original network and a directed hyper-edge encodes estimated influence flow be-
tween communities (derived from cross-community diffusion patterns or inter-community live-edge fre-
quency).
Such a representation enables principled selection of candidate communities by:
• Distance-based diversification: selecting communities that are structurally distant in the hyper-
graph to maximize coverage and minimize redundancy.
• Hypergraph clustering: grouping communities into higher-level modules and selecting the most
influential representatives from each cluster.
• Influence-aware pruning: discarding communities whose outgoing hypergraph influence is neg-
ligible, thereby reducing the search space.
This high-level abstraction may further reduce computation by shifting seed selection from the node
level to the community-selection level.

b. Reducing Monte Carlo Simulations via Diffusion-Aware Surrogates

Inspired by CoFIM, PRTH/PRDD, and ILP-based frameworks, our future work aims to replace repeated
Monte Carlo (MC) simulations with more scalable, diffusion-aware surrogate functions. Potential direc-
tions include:
• Submodular approximations of influence: designing a surrogate objective similar to CoFIM’s
community-activation function but tailored to our PageRank-based pipeline.
• Component-driven influence estimation: computing influence as the expected component size
over a small number of live-edge samples, using soft memberships between nodes and components
to interpolate influence without many MC runs.
• Dynamic marginal-gain estimation: estimating marginal gains from structural signals (PageR-
ank, local expansion, hypergraph neighborhoods) rather than repeated IC simulations.
The goal is to preserve the accuracy of greedy IM while reducing MC evaluations by one or two
orders of magnitude.

34
c. Improving Community Quality and Controllability
The scalability and effectiveness of community-aware seed selection depend heavily on the quality and
granularity of detected communities. Several improvements can be pursued:
• Refined community generation: experimenting with algorithms that allow explicit control over
size, density, and resolution (e.g., Leiden, Louvain with resolution parameter, hierarchical In-
fomap).

• Adaptive community splitting: breaking overly large communities into medium-sized, diffusion-
relevant subcommunities using conductance or boundary sparsity criteria.

• Community merging: combining small, low-influence communities into aggregate modules to

reduce noise and limit the number of candidate regions.

• Quality-driven filtering: selecting communities based on measures such as inter/intra influence

ratio, hypergraph centrality, or local branching factor.
These techniques help ensure that communities reflect meaningful diffusion boundaries and remain
compatible with scalable seed selection.

d. Towards a Unified Scalable IM Framework

Combining the above ideas leads to the long-term goal of building a unified, community-driven influence
maximization system that:
1. operates on community hypergraphs,

2. uses PageRank variants to generate strong candidate seeds, and

3. relies on diffusion-aware surrogates to approximate greedy behavior efficiently.

Such a framework would significantly reduce computational overhead while maintaining high-quality
influence spread, making it practical for networks with tens of millions of nodes.

References
[1] Kempe, D., Kleinberg, J., & Tardos, É. (2003). Maximizing the spread of influence through a
social network. In Proceedings of the ninth ACM SIGKDD international conference on Knowledge
discovery and data mining (pp. 137-146).

[2] Chen, W., Wang, Y., & Yang, S. (2009). Efficient influence maximization in social networks. In
Proceedings of the 15th ACM SIGKDD international conference on Knowledge discovery and data
mining (pp. 199-208).

[3] Leskovec, J., Krause, A., Guestrin, C., Faloutsos, C., Faloutsos, M., & Glance, N. (2007). Cost-
effective outbreak detection in networks. In Proceedings of the 13th ACM SIGKDD international
conference on Knowledge discovery and data mining (pp. 420-429). [CELF Algorithm]

[4] Borgs, C., Brautbar, M., Chayes, J., & Lucier, B. (2014). Maximizing social influence in nearly
optimal time. In Proceedings of the twenty-fifth annual ACM-SIAM symposium on Discrete algo-
rithms (pp. 946-957). [RIS Algorithm]

[5] Rosvall, M., & Bergstrom, C. T. (2008). Maps of random walks on complex networks reveal com-
munity structure. Proceedings of the National Academy of Sciences, 105(4), 1118-1123. [Infomap
Algorithm]

35
 [6] Blondel, V. D., Guillaume, J. L., Lambiotte, R., & Lefebvre, E. (2008). Fast unfolding of com-
munities in large networks. Journal of Statistical Mechanics: Theory and Experiment, 2008(10),
P10008. [Louvain Method]

[7] Page, L., Brin, S., Motwani, R., & Winograd, T. (1999). The PageRank citation ranking: Bringing
order to the web. (Technical Report). Stanford InfoLab.

[8] Kleinberg, J. M. (1999). Authoritative sources in a hyperlinked environment. Journal of the ACM
(JACM), 46(5), 604-632. [HITS Algorithm]

[9] Nemhauser, G. L., Wolsey, L. A., & Fisher, M. L. (1978). An analysis of approximations for
maximizing submodular set functions—I. Mathematical Programming, 14(1), 265-294.

[10] J. Chen, J. Lei, and X. Xiao, “Influence Maximization via PageRank-Based Selection Strategies,”
Proceedings of the 33rd International Conference on Software Engineering and Knowledge Engi-
neering (SEKE), 2021, pp. 145–150.

[11] Y. Shang, J. Lou, and J. Chen, “CoFIM: A Community-Based Framework for Influence Maximiza-
tion on Large-Scale Networks,” Knowledge-Based Systems, vol. 124, pp. 63–73, 2017.

[12] J. Pattanayak, R. S. Thakur, and B. Pati, “A Community-Aware Framework for Social Influence
Maximization,” 2022 IEEE International Conference on Big Data (BigData), pp. 588–597, 2022.

36