Local Influence: Bridging Community Detection and Influence Maximization

TL;DR

Social communities aren't just random clusters; they are formed around influential "founders." This paper presents a unified framework that uses a novel Local Influence metric—calculating importance through direct, indirect, and triangle-based neighbor relationships—to solve both influence maximization and community detection. It supports overlapping and hierarchical structures and can process 300k+ nodes in under two minutes.

Problem & Motivation: The "Why" of Social Formation

Prior works in community detection often treat the task as a purely mathematical partitioning problem (like Modularity optimization) or a label propagation task. However, they miss the formative logic of social networks: communities usually gather around influential individuals (founders).

In influence maximization, standard heuristics like Degree Centrality are often too coarse. A node with many neighbors might not be truly influential if its neighbors are all connected to each other, creating a "bottleneck" of redundant influence. The authors argue that we need to quantify how a node affects its local environment, specifically looking at the triangle structures that signify strong social cohesion.

Methodology: The Core Architecture

The heartbeat of this framework is the Local Influence formula ($E_{ij}$), which determines the influence of node $j$ on node $i$.

1. Quantifying Local Influence

The formula consists of three specific components:

• Direct Influence: The basic link between immediate neighbors.
• Indirect Influence: Information exchange through common neighbors.
• Enhancement Influence: A "bonus" score if the nodes are part of a triangle, representing the psychological reinforcement of group peers.

Fig 1: The orientation of local influence. Note that $E_{ij}eq{E}_{ji}$, as influence is dependent on the target node's degree and receptor capacity.

2. The Step-by-Step Algorithm

The framework operates in a cycle:

1. Founder Selection: Find the node with the highest total Local Influence.
2. Core Formation: The founder gathers its neighbors to form a "community core."
3. Influence Diffusion: Using a Linear Threshold Model, the community expands. Nodes join if their perceived influence from the community exceeds a "join threshold" ($\gamma$).

Experiments & Results

The authors validated their approach on real-world datasets like the Enron-Email network and DBLP research collaborations.

Influence Maximization Performance

Compared to SOTA heuristics like MDD and Local Centrality, the Local Influence method showed faster convergence and wider diffusion spread.

Fig 2: Diffusion ranges on Enron-Email and Cond-mat. The Local Influence method (Red) stays consistently above traditional heuristics.

Community Detection Efficiency

On the DBLP network (317,080 nodes, ~1M edges), the algorithm achieved:

• Peak Modularity: 0.70 at $\gamma =0.41$.
• Speed: Total execution in 120 seconds on a standard PC.
• Hierarchy: By adjusting the $\gamma$ threshold, the algorithm naturally reveals hierarchical community levels without re-running the heavy influence calculations.

Critical Analysis & Conclusion

Takeaway

The genius of this paper lies in its uniformity. By treating community detection as a derivative of influence maximization, the authors provide a more "natural" simulation of social group formation. The $O(n⟨k{⟩}^3)$ complexity makes it remarkably viable for the massive graphs seen in contemporary social media.

Limitations & Future Work

While effective, the parameters $\alpha$ (attenuation) and $\beta$ (enhancement) are currently fixed based on empirical observation. A future extension could involve automated parameter tuning or learning these weights via Graph Neural Networks (GNNs) based on specific network types (e.g., distinguishing between a professional LinkedIn network vs. a casual Twitter network).