To Be Connected, or Not to Be Connected

Abstract

We study the problem of extracting a selective connector for a given set of query vertices Q subset of V in a graph G = (V,E). A selective connector is a subgraph of G which exhibits some cohesiveness property, and contains the query vertices but does not necessarily connect them all. Relaxing the connectedness requirement allows the connector to detect multiple communities and to be tolerant to outliers. We achieve this by introducing the new measure of network inefficiency and by instantiating our search for a selective connector as the problem of finding the minimum inefficiency subgraph.