Degree Centrality-Based Influence Maximization by Community Detection and Finding Bridging Nodes

Degree centrality is one of the simplest centrality metrics used to rank the nodes of a network, which in-turn helps in selecting the most influential nodes for influence maximization. The centrality measures such as betweenness centrality measure have better spreading with higher computational complexity. Whereas, centrality measures such as degree have lower computational complexity with inferior spreading. In this work, we a have partitioned the network to create communities (clusters) of nodes, and formed abstract network with communities as super nodes. We have ranked the super nodes based on their degree centrality, with respect to the abstract network. The total seed nodes are distributed across the the communities. The community with greater degree centrality is given preference for allocation of seed nodes. Inside each community, higher preference is given to the nodes with higher degree and better connectivity to nodes outside its own community . In-terms of computational complexity, the proposed method is similar to degree centrality; whereas, in-terms of spreading, its is either comparable or supersedes betweenness centrality for few networks.