A Study Of Closeness Metric For Social Networks

On the basis of analysis of existing metric, we axiomatically develop a new metric of personal connection between individuals in social networks based on the k shortest paths. Our metric can be considered as a generalization of metrics based on the shortest path. It involves more useful connecting information between individuals, and assigns appropriate weights to different shortest paths. Hence, the metric is able to distinguish the closeness between nodes more relevantly than traditional metrics. To guarantee the correctness of our metric, we propose several criteria which the metric should meet, and then it is proved that our defined metric satisfying these criteria meets the metric axioms. Subsequently, we study the problem how to assign appropriate weights on different shortest paths. In the process, we creatively put forward a concept of the spread of metric, and construct a convex optimization model with it as the target function to solve the weight in the metric definition. Profiting from the convex model, our metric is able to assign appropriate weight on the k shortest paths according to the characteristics of different networks, so it has a strong adaptability to different networks. Aiming at reducing the complexity to the convex model, three improved models are proposed by the deletion of invalid constraints or reinforcement of current constraints, so that these models get more practical. Finally, the algorithms are implemented and evaluated on random networks and real social networks data. The results demonstrate relevance and correctness of our formalization.