Maximal assortative matching for real-world network graphs, random network graphs and scale-free network graphs

详细信息    查看全文

• 作者：Natarajan Meghanathan
• 刊名：Vietnam Journal of Computer Science
• 出版年：2016
• 出版时间：August 2016
• 年：2016
• 卷：3
• 期：3
• 页码：151-179
• 全文大小：11,843 KB
• 刊物类别：Information Systems and Communication Service; Artificial Intelligence (incl. Robotics); Computer Ap
• 刊物主题：Information Systems and Communication Service; Artificial Intelligence (incl. Robotics); Computer Applications; e-Commerce/e-business; Computer Systems Organization and Communication Networks; Computa
• 出版者：Springer Berlin Heidelberg
• ISSN：2196-8896
• 卷排序：3

文摘

We define the problem of maximal assortativity matching (MAM) as a variant of the maximal matching problem wherein we want to maximize the similarity between the end vertices (with respect to any particular measure for node weight) constituting the matching. The MAM algorithm (with a targeted assortative index value of 1) works on the basis of the assortative weight of an edge, defined as the product of the number of uncovered adjacent edges and the absolute difference of the weights of the end vertices of the edge. The MAM algorithm prefers to include the edge with the smallest assortativity weight (the assortative weight of the edges is updated for each iteration) until all the edges in the graph are covered. We show that the MAM algorithm can be easily adapted to be used for maximal dissortative matching (MDM) with a targeted assortative index of \(-\)1 for the matching as well as for maximal node matching (MNM) algorithm to maximize the percentage of nodes matched. We illustrate the execution of the MAM, MDM and MNM algorithms on complex network graphs such as the random network graphs and scale-free network graphs as well as on real-world network graphs and analyze the tradeoffs.KeywordsMaximal matchingAssortative matchingDissortative matchingAssortativity indexComplex networks Independent edge setNode similarityRandom networks Scale-free networks