Maximizing Network Performance Based on Group Centrality by Creating Most Effective k-Links

Group centrality is an extension of the conventional node centrality in which the importance of a group of nodes together is the target for performance evaluation. We used this notion and formulated a link creation problem to a spatial network. The kind of problem we want to solve is to find the best places to construct k new roads to maximize the evacuation performance. The problem is formulated as an optimization problem to maximize the gain of the group closeness centrality by creating a set of new roads (k links) with the constraints on the road range distance (link length limit Δ). The problem is NP-hard. We show that this problem is reduced to a node selection problem and the objective function is submodular when there is no constraint on the link length limit. We devised an efficient greedy algorithm to search for the best k new roads under the constraint of Δ that comprises three steps: centrality calculation, parents selection and nodes selection. We applied this algorithm to three real road networks of different cities and evaluated its performance with respect to k and Δ. The algorithm is quite efficient and obtains the efficiency gain of 10^3 to 10^6 compared with a naive method in which every single node is blindly tested as a candidate from which to create a new road.