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

Meghanathan, Natarajan

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.

STATISTICAL matching; SCALE-free network (Statistical physics); GRAPH algorithms; GRAPHIC methods in statistics; GEOMETRIC vertices; MAXIMAL functions

Vietnam Journal of Computer Science (Springer Nature), 2016, Vol 3, Issue 3, p151

2196-8888

Academic Journal

10.1007/s40595-016-0066-0