Maximal Assortative Matching and Maximal Dissortative Matching for Complex Network Graphs

摘要

Matching of vertices in social networks and other complex networks needs to take into consideration the weight of the vertices (like degree) that are matched; arbitrary matching of the vertices with simply the objective of maximizing the number of vertices need not be of any practical benefit. Assor-tativity of the edges in a network is a measure of the similarity of the end vertices of the edges with respect to any measure of node weight and is quantified in terms of the assortative index. In this paper, we propose to apply the notion of assortativity for one-to-one matching of the vertices such that the assortativity of the matching is maximized or minimized as much as possible, depending on the case. We design algorithms for maximal assortative matching (MAM, to maximize the assortativity index (AI)) and maximal dissortative matching (MDM, to minimize the assortative index) for complex network graphs and compare their performance with that of a maximal node matching (MNM) algorithm that aims to simply maximize the percentage of nodes matched. We execute the MAM, MDM and MNM algorithms on real-world network graphs as well as on theoretically generated complex network graphs and analyze the performance tradeoffs with respect to the percentage of node matches and AI.