Affiliations: [a] College of Computer Science and Technology, Jilin University, Changchun, Jilin, China | [b] Key Laboratory of Symbol Computation and Knowledge Engineering of the Ministry of Education, Jilin University, Changchun, Jilin, China
Correspondence:
[*]
Corresponding author: Bo Yang, College of Computer Science and Technology, Jilin University, Changchun 130012, Jilin, China. E-mail: [email protected].
Abstract: Given a network and a group of target nodes, the task of proximity alignment is to find out a sequence of nodes that are the most relevant to the targets in terms of the linkage structure of the network. Proximity alignment will find important applications in many areas such as online recommendation in e-commerce and infectious disease controlling in public healthcare. In spite of great efforts having been made to design various metrics of similarities and centralities in terms of network structure, to the best of our knowledge, there have been no studies in the literature that address the issue of proximity alignment by explicitly and adequately exploring the intrinsic connections between macroscopic community structure and microscopic node proximities. However, the influence of community structure on proximity alignment is indispensable not only because they are ubiquitous in real-world networks but also they can characterize node proximity in a more natural way. In this work, a novel proximity alignment method called the PAA is proposed to address this problem. The PAA first decomposes the given network into communities based on its global structure and then compute node proximities based on the local structure of communities. In this way, the solution of the PAA is expected to be more reasonable in the sense of both global and local relevance among nodes being sufficiently considered during the process of proximity aligning. To handle large-scale networks, the PAA is implemented by a proposed online-offline schema, in which expensive computations such as community detection will be done offline so that online queries can be quickly responded by calculating node proximities in an efficient way based on indexed communities. The efficacy and the applications of the PAA have been validated and demonstrated. Our work shows that the PAA outperforms existing methods and enables us to explore real-world networks from a novel perspective.
Keywords: Proximity alignment, community detection, ranking, similarity, social network analysis, recommender system
