Edge Augmentation on Disconnected Graphs via Eigenvalue Elevation. (arXiv:2207.05301v1 [cs.SI])

The graph-theoretical task of determining most likely inter-community edges
based on disconnected subgraphs' intra-community connectivity is proposed. An
algorithm is developed for this edge augmentation task, based on elevating the
zero eigenvalues of graph's spectrum. Upper bounds for eigenvalue elevation
amplitude and for the corresponding augmented edge density are derived and are
authenticated with simulation on random graphs. The algorithm works
consistently across synthetic and real networks, yielding desirable performance
at connecting graph components. Edge augmentation reverse-engineers graph
partition under …

arxiv augmentation edge eigenvalue graphs