We found a match
Your institution may have access to this item. Find your institution then sign in to continue.
- Title
Maximal assortative matching for real-world network graphs, random network graphs and scale-free network graphs.
- Authors
Meghanathan, Natarajan
- Abstract
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.
- Subjects
STATISTICAL matching; SCALE-free network (Statistical physics); GRAPH algorithms; GRAPHIC methods in statistics; GEOMETRIC vertices; MAXIMAL functions
- Publication
Vietnam Journal of Computer Science (Springer Nature), 2016, Vol 3, Issue 3, p151
- ISSN
2196-8888
- Publication type
Academic Journal
- DOI
10.1007/s40595-016-0066-0