Ultra-small world detection in networks: subgraphs with prescribed distance distributions

Abstract We introduce a class of distance-based clique relaxation models, which enforce certain distributions on vertex pairwise distances in the corresponding induced subgraphs. Both “local” and “global” versions of the proposed approach are studied. For the global case, the distribution of distances is considered for all vertex pairs in the subgraph. For the local (and, in a sense, more restrictive) case, the required property must be satisfied for any vertex with respect to its distances to the other vertices in the subgraph. We refer to the proposed clique relaxations as global and local $$\varvec{\gamma }$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>γ</mml:mi> </mml:mrow> </mml:math> - ultra-small worlds , respectively, where parameter $$\varvec{\gamma }$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>γ</mml:mi> </mml:mrow> </mml:math> controls the required distance distributions. Our modeling approach has several meaningful interpretations; in particular, it is closely related to the concept of an “effective” graph diameter. Furthermore, density- and degree-based quasi-cliques are two well-known special cases of the proposed concept. We exploit these relationships to develop mixed integer programs (MIPs) that can be used with an off-the-shelf solver for finding maximum global and local ultra-small worlds. Then, we outline a simple-to-implement algorithm that iteratively solves feasibility versions of our MIPs for each possible subgraph size within some lower and upper bounds; we derive one non-trivial upper bound using the linear programming relaxations. Our modeling approach also generalizes the k -club concept; hence, some links to this well-known distance-based clique relaxation are also explored. Finally, to illustrate the obtained results, we perform a computational study on graphs representing various types of real-world datasets and systems. Some interesting empirical observations and insights are provided.