Identifying the most influential nodes in a massive social network—a problem known as Influence Maximization (IM)—is computationally expensive and often hindered by incomplete data. Traditional approaches treat networks as monolithic structures, but real-world graphs are modular, composed of dense clusters (communities) connected by sparse links. Recent research demonstrates that this community structure is not just a feature to be mapped, but a powerful mechanism to bypass computational bottlenecks and infer influence in "black-box" environments where the network structure is unknown.
The Modularity Shortcut
The primary reason community-aware algorithms outperform global ones is modularity. When a network is partitioned into tight, well-defined communities, the global problem of influence propagation can be decomposed into independent local sub-problems.
Umrawal et al. show that by solving IM locally within communities and then using "progressive budgeting" to allocate seeds globally, one can achieve massive speedups with negligible loss in accuracy. The intuition is that a node’s influence is most potent within its own cluster; therefore, identifying local leaders is a highly effective proxy for finding global influencers. This divide-and-conquer strategy is also applied to centrality metrics. Erdös et al. demonstrate that by summarizing communities into a "skeleton graph," the heavy lifting of calculating betweenness centrality can be performed on a much smaller scale, resulting in speedups of up to 75x.
Local Cores Over Global Hubs
A common misconception in network science is that high-degree "hubs"—nodes with the most total connections—are always the best initiators of information. However, community-centric metrics suggest otherwise.
Chakraborty et al. introduced the concept of permanence, a vertex-centric metric that quantifies how strongly a node belongs to its specific community. They argue that nodes deeply embedded in their local clusters (high permanence) are more effective seeds than those with high global connectivity but weak community ties. Because these "core" nodes are more effectively connected to their immediate neighbors, they can trigger a rapid local cascade that eventually spills over into the rest of the network.
When information must travel between clusters, the choice of "bridge" nodes becomes critical. Das et al. found that to minimize delays in a "Network of Networks," bridge nodes should be selected based on their information centrality within their local clusters. This ensures that once information reaches a cluster, it synchronizes with the rest of the sub-network as quickly as possible, minimizing the bottleneck effect of sparse inter-community links.
Influencing the Unknown
In many real-world scenarios, such as public health interventions, the underlying social network is unknown and expensive to map. Community structure provides a way to "learn" influence from limited samples or queries.
The ARISEN algorithm, proposed by Wilder et al., leverages the fact that real-world networks are modular to identify influencers by querying only a tiny fraction of the population. In a random graph, you would need to see almost the entire network to find the best seeds. In a clustered network, however, finding a few members of a dense community allows the algorithm to quickly locate the "local stars" who drive the most influence.
Furthermore, Balkanski et al. show that observing past cascades (information spreading from node to node) is sufficient to identify high-quality seed sets without ever seeing a map of the network. Their COPS algorithm treats communities as discrete units where a single seed can reliably trigger a cluster-wide cascade. This allows researchers to bypass theoretical "impossibility" results that apply to unstructured graphs, proving that the natural organization of human society into communities makes the influence problem far more tractable than it appears in the worst-case mathematical models.
Key Foundational Work
Permanence and Community Structure in Complex Networks (2016) — contributed 1 concept elements to this direction.
GenPerm: A Unified Method for Detecting Non-overlapping and Overlapping Communities (2016) — contributed 1 concept elements to this direction.
A Divide-and-Conquer Algorithm for Betweenness Centrality (2014) — contributed 1 concept elements to this direction.