Greedily Improving Our Own Centrality in A Network

摘要: The closeness and the betweenness centralities are two well-known measures of importance a vertex within given complex network. Having high or centrality can have positive impact on itself: hence, in this paper we consider problem determining how much increase its by creating limited amount new edges incident to it. We first prove that does not admit polynomial-time approximation scheme unless $$P=NP$$, then propose simple greedy algorithm with an almost tight ratio, whose performance is tested synthetic graphs real-world networks.