CONSTRAINED SEED SELECTION FOR INFLUENCE MAXIMIZATION: A COMPARATIVE STUDY OF HYBRID CENTRALITY MEASURES

Abstract

The problem of identifying a compact set of influential nodes in a complex network underlies several applications such as epidemic control, viral marketing, rumour sup pression, and infrastructure protection. A common approach is to rank nodes by some structural centrality and pick the top-k as seeds. The well-known shortcoming is that the highest ranked nodes tend to cluster in the dense core of real networks, leading to overlapping influence regions and to a non-redundant reach that falls short of what the same budget could otherwise achieve. A recent proposal known as Core-Flow Centrality (CF) addresses this in two ways. The first is a weighted blend of normalised M-shell and normalised Betweenness Centrality, with a reported optimum at α = 0.6. The second is an Improved Core-Flow (ICF) procedure that walks down the CF-ranked list and rejects any candidate whose shortest path distance to an already-selected seed is less than two hops. The original work claimed that CF outperforms structural baselines in Kendall’s τ against SIR ground truth, that the α = 0.6 peak is consistent across networks, and that CF combined with ICF achieves the largest influence spread on a standard five-network benchmark. This thesis presents an end-to-end reproduction of those claims on the same five datasets (NetScience, C. Elegans, Jazz, PowerGrid, and AstroPh) using the paper’s stated proto col. The implementation includes a from-scratch Zeng–Zhang M-shell decomposition, an efficient ICF routine based on truncated breadth-first search, a deterministically seeded SIR simulator with repeated random runs, and a sparse adjacency eigensolver for the infection-rate calibration. Two findings emerge. Under faithful reproduction, CF does not outperform pure M-shell in Kendall’s τ on any of the five networks; the α-sweep is monotonic in α with the peak at α = 1.0, and a normalisation sensitivity analysis spanning min-max, z-score, and rank schemes confirms the result is not an artefact of normalisation choice. By contrast, the distance constraint of the ICF model is faithfully replicated, in that each centrality derives the benefit of two hops of separation, resulting in an improvement of influence spread at p = 5% for PowerGrid between 19% (for M-shell) and 56% (for θ). As aconsequence, the only useful aspect of the initial proposal is the distance constraint, not the hybrid centrality. M-shell combined with ICF emerges as a simpler and equally effective alternative to CF combined with ICF.