[IEEE Access] Identifying Influential Individuals via Community-Based Network Embedding

TL;DR

Identifying the most influential nodes in a massive social network (Influence Maximization) is a balancing act between mathematical rigor and computational feasibility. This paper introduces ICRIM, an algorithm that uses Network Embedding to detect communities and restricts greedy search to these local structures. The result? A method that is 1,000x faster than traditional greedy approaches while retaining a provable performance guarantee.

Problem & Motivation: The Greedy Bottleneck

In viral marketing, the goal is to pick $k$ "seed" nodes to maximize the "word-of-mouth" effect. Since 2003, we've known this problem is NP-hard.

• The Greedy Solution: Picking the best node iteratively gives a great result (within 63% of optimal), but it requires millions of slow Monte Carlo simulations.
• The Heuristic Solution: Fast methods (like picking high-degree nodes) are unstable and often miss the true "influencers."
• The Insight: Social networks aren't random; they are made of communities. If we can find these communities and account for the "hubs" that bridge them, we can solve the problem locally without losing global impact.

Methodology: Embedding and Lazy Greed

The authors propose a two-step framework designed for scalability.

1. NECD (Network Embedding based Community Detection)

Instead of using classic topological clustering, the authors use LINE (Large-scale Information Network Embedding). This transforms the graph into a low-dimensional vector space where nodes with similar roles are close together. They then apply $k$-means to these vectors, which captures community structures more accurately than traditional modularity-based methods.

2. ICRIM (Improved Community-based Robust Influence Maximization)

The core innovation is how ICRIM estimates "Marginal Gain." Instead of simulating a node's influence across the entire network, ICRIM limits the scope to the node's own community and its neighbors' communities.

Figure 1: The two-phase framework: Community detection via embedding, followed by localized seed selection.

To further boost speed, they implement a Lazy Operation. Since the marginal gain of a node can only decrease as more seeds are added (the Submodularity property), the algorithm uses a priority queue to avoid re-calculating the influence of nodes that are unlikely to be the new top choice.

Experiments & Results

The authors tested their method against heavyweights like CELF++ and IMRank across small (Facebook) and large (Youtube, 1.1M nodes) datasets.

Speed vs. Quality

On the Epinions dataset, while the standard Greedy approach took several days, ICRIM finished in less than 2 minutes. Crucially, the "Influence Spread" (the number of people reached) was nearly identical to the slow greedy methods.

Figure 2: Running time on small networks. Note the logarithmic scale: ICRIM (red) is consistently several orders of magnitude faster than CELF++ (black).

The Power of Hubs

A unique feature of this work is its treatment of Hub nodes. By allowing hub nodes to influence adjacent communities (as shown in the toy network in the paper), ICRIM captures "bridge" influencers that standard community-clustering methods often ignore.

Critical Analysis & Conclusion

Takeaway

ICRIM proves that you don't need to simulate the whole world to understand a single person's impact. By using Network Embedding to define the boundaries of influence, we can turn a multi-day computation into a multi-minute task.

Limitations & Future Work

The current approach for the Linear Threshold (LT) model is still significantly slower than the Independent Cascade (IC) model, taking several days on million-node graphs. Future research will likely focus on optimizing the LT model simulations and exploring how this localized greedy approach handles "Friend and Foe" relationships or polarized networks.

In conclusion, this work provides a robust bridge between high-theory greedy algorithms and the practical needs of large-scale social media analytics.