Wiener connector

In network theory, the Wiener connector is a means of maximizing efficiency in connecting specified "query vertices" in a network. Given a connected, undirected graph and a set of query vertices in a graph, the minimum Wiener connector is an induced subgraph that connects the query vertices and minimizes the sum of shortest path distances among all pairs of vertices in the subgraph. In combinatorial optimization, the minimum Wiener connector problem is the problem of finding the minimum Wiener connector. It can be thought of as a version of the classic Steiner tree problem (one of Karp's 21 NP-complete problems), where instead of minimizing the size of the tree, the objective is to minimize the distances in the subgraph.

The minimum Wiener connector was first presented by Ruchansky et al. in 2015.

The minimum Wiener connector has applications in many domains where there is a graph structure and an interest in learning about connections between sets of individuals. For example, given a set of patients infected with a viral disease, which other patients should be checked to find the culprit? Or given a set of proteins of interest, which other proteins participate in pathways with them?

The Wiener connector was named in honor of chemist Harry Wiener who first introduced the Wiener Index.

Problem definition

The Wiener index is the sum of shortest path distances in a (sub)graph. Using [math]\displaystyle{ d(u,v) }[/math] to denote the shortest path between [math]\displaystyle{ u }[/math] and [math]\displaystyle{ v }[/math], the Wiener index of a (sub)graph [math]\displaystyle{ S }[/math], denoted [math]\displaystyle{ W(S) }[/math], is defined as

[math]\displaystyle{ W(S) = \sum_{(u, v) \in S} d(u,v) }[/math].

The minimum Wiener connector problem is defined as follows. Given an undirected and unweighted graph with vertex set [math]\displaystyle{ V }[/math] and edge set [math]\displaystyle{ E }[/math] and a set of query vertices [math]\displaystyle{ Q\subseteq V }[/math], find a connector [math]\displaystyle{ H\subseteq V }[/math] of minimum Wiener index. More formally, the problem is to compute

[math]\displaystyle{ \operatorname*{arg\,min}_H W(H\cup Q) }[/math],

that is, find a connector [math]\displaystyle{ H }[/math] that minimizes the sum of shortest paths in [math]\displaystyle{ H }[/math].

Relationship to Steiner tree

The optimal solutions to the Steiner tree problem and the minimum Wiener connector can differ. Define the set of query vertices Q by Q = {v₁, ..., v₁₀}. The unique optimal solution to the Steiner tree problem is Q itself, which has Wiener index 165, whereas the optimal solution for the minimum Wiener connector problem is Q ∪ {r₁, r₂}, which has Wiener index 142.

The minimum Wiener connector problem is related to the Steiner tree problem. In the former, the objective function in the minimization is the Wiener index of the connector, whereas in the latter, the objective function is the sum of the weights of the edges in the connector. The optimum solutions to these problems may differ, given the same graph and set of query vertices. In fact, a solution for the Steiner tree problem may be arbitrarily bad for the minimum Wiener connector problem; the graph on the right provides an example.

Computational complexity

Hardness

The problem is NP-hard, and does not admit a polynomial-time approximation scheme unless P = NP. This can be proven using the inapproximability of vertex cover in bounded degree graphs. Although there is no polynomial-time approximation scheme, there is a polynomial-time constant-factor approximation—an algorithm that finds a connector whose Wiener index is within a constant multiplicative factor of the Wiener index of the optimum connector. In terms of complexity classes, the minimum Wiener connector problem is in APX but is not in PTAS unless P = NP.

Exact algorithms

An exhaustive search over all possible subsets of vertices to find the one that induces the connector of minimum Wiener index yields an algorithm that finds the optimum solution in [math]\displaystyle{ 2^{O(n)} }[/math] time (that is, exponential time) on graphs with n vertices. In the special case that there are exactly two query vertices, the optimum solution is the shortest path joining the two vertices, so the problem can be solved in polynomial time by computing the shortest path. In fact, for any fixed constant number of query vertices, an optimum solution can be found in polynomial time.

Approximation algorithms

There is a constant-factor approximation algorithm for the minimum Wiener connector problem that runs in time [math]\displaystyle{ O(q (m \log n + n \log^2 n)) }[/math] on a graph with n vertices, m edges, and q query vertices, roughly the same time it takes to compute shortest-path distances from the query vertices to every other vertex in the graph. The central approach of this algorithm is to reduce the problem to the vertex-weighted Steiner tree problem, which admits a constant-factor approximation in particular instances related to the minimum Wiener connector problem.

Behavior

The minimum Wiener connector behaves like betweenness centrality.

When the query vertices belong to the same community, the non-query vertices that form the minimum Wiener connector tend to belong to the same community and have high centrality within the community. Such vertices are likely to be influential vertices playing leadership roles in the community. In a social network, these influential vertices might be good users for spreading information or to target in a viral marketing campaign.

When the query vertices belong to different communities, the non-query vertices that form the minimum Wiener connector contain vertices adjacent to edges that bridge the different communities. These vertices span a structural hole in the graph and are important.

Applications

The minimum Wiener connector is useful in applications in which one wishes to learn about the relationship between a set of vertices in a graph. For example,

• in biology, it provides insight into how a set of proteins in a protein–protein interaction network are related,
• in social networks (like Twitter), it demonstrates the communities to which a set of users belong and how these communities are related,
• in computer networks, it may be useful in identifying an efficient way to route a multicast message to a set of destinations.