Algorithm and Complexity for a Network Assortativity Measure

Abstract

We show that finding a graph realization with the minimum Randić index for a given degree sequence is solvable in polynomial time by formulating the problem as a minimum weight perfect b-matching problem. However, the realization found via this reduction is not guaranteed to be connected. Approximating the minimum weight b-matching problem subject to a connectivity constraint is shown to be NP-Hard. For instances in which the optimal solution to the minimum Randić index problem is not connected, we describe a heuristic to connect the graph using pairwise edge exchanges that preserves the degree sequence. In our computational experiments, the heuristic performs well and the Randić index of the realization after our heuristic is within 3% of the unconstrained optimal value on average. Although we focus on minimizing the Randić index, our results extend to maximizing the Randić index as well. Applications of the Randić index to synchronization of neuronal networks controlling respiration in mammals and to normalizing cortical thickness networks in diagnosing individuals with dementia are provided.

Added additional section on applications