Finding Influential Nodes in Social Networks Using Minimum k-Hop Dominating Set

摘要

Challenges in social interaction networks are often modelled as graph theoretic problems. One such problem is to find a group of influential individuals of minimum size or the initial seed set in a social network, so that all the nodes in the network can be reached with only one hop from the seeds. This problem is equivalent to finding a minimum dominating set for the network. In this paper, we address a problem which is similar to finding minimum dominating set but differs in terms of number of hops needed to reach all the nodes. We have generalized the problem as k-hop dominating set problem, where a maximum of k hops will be allowed to spread the information among all the nodes of the graph. We show that the decision version of the k-hop dominating set problem is NP-complete. Results show that, in order to reach the same percentage of nodes in the network, if one extra hop is allowed then the cardinality of the seed set i.e. the number of influential nodes needed, is considerably reduced. Also, the experimental results show that the influential nodes can be characterized by their high betweenness values.