Journal
JOURNAL OF KING SAUD UNIVERSITY-COMPUTER AND INFORMATION SCIENCES
Volume 28, Issue 2, Pages 230-246Publisher
ELSEVIER
DOI: 10.1016/j.jksuci.2015.10.004
Keywords
Maximal matching; Assortative matching; Dissortative matching; Assortativity index; Complex networks; Node similarity
Categories
Funding
- NASA EPSCoR sub award from University of Mississippi [NNX14AN38A]
- NASA [679189, NNX14AN38A] Funding Source: Federal RePORTER
Ask authors/readers for more resources
We define the problem of maximal assortativity matching (MAM) for a complex network graph as the problem of maximizing the similarity of the end vertices (with respect to some measure of node weight) constituting the matching. In this pursuit, we introduce a metric called the assortativity weight of an edge, defined as the product of the number of uncovered adjacent edges and the absolute value of the difference in the weights of the end vertices. The MAM algorithm prefers to include edges that have the smallest assortativity weight in each iteration (one edge per iteration) until all edges are covered. The MAM algorithm can also be adapted to determine a maximal dissortative matching (MDM) to maximize the dissimilarity between the end vertices that are part of a matching as well as to determine a maximal node matching (MNM) that simply maximizes the number of vertices that are part of the matching. We run the MAM, MNM and MDM algorithms on real-world network graphs as well as on the theoretical model-based random network graphs and scale-free network graphs and analyze the tradeoffs between the% of node matches and assortativity index (targeted optimal values: 1 for MAM and -1 for MDM). (C) 2015 The Author. Production and hosting by Elsevier B.V. on behalf of King Saud University.
Authors
I am an author on this paper
Click your name to claim this paper and add it to your profile.
Reviews
Recommended
No Data Available