Is it the same as a Steiner tree?

No. A Steiner-tree objective typically minimizes connection cost, while this objective minimizes an all-pairs distance sum in the connector.

Can an added node make the score worse?

Yes. The leaf T does so in the worked example.

Does the method require the query vertices to form one existing community?

No. The connector can link query vertices from different parts of the graph.

AI Glossary / Data science and analytics / Advanced

Wiener connector

Definition

A Wiener connector is a connected subgraph containing a specified set of query vertices, considered under an objective based on its Wiener index. The minimum Wiener connector minimizes the sum of shortest-path distances over all unordered pairs of vertices in the chosen subgraph. The objective includes added connector vertices, not only the query vertices.

What it means

A large network may contain a few nodes of particular interest. The task is to extract a connected part that includes those nodes while keeping its overall pairwise distances small. Additional nodes may be necessary to connect the query set or provide useful shortcuts.
This differs from simply drawing a separate shortest path between every query pair. Those paths can combine into a large subgraph whose additional vertices also contribute to the objective.
The original formulation studied by Ruchansky and colleagues uses connected, undirected, unweighted graphs. Its minimum is an optimization result under that model. It does not automatically identify the most meaningful explanation of a real-world relationship.

How it works

Specify a graph G and query set Q. A feasible solution chooses a vertex set S containing Q such that the induced subgraph G[S] is connected. Induced means retaining every original edge whose endpoints both belong to S.
Measure shortest-path distances inside that selected subgraph and sum them across unordered pairs. Paths cannot take shortcuts through vertices outside S. Compare feasible solutions using this total, rather than just their number of edges or query-to-query distances.
Adding a vertex can shorten existing distances but also creates new pairs to count. This trade-off discourages unnecessary expansion without fixing a separate size budget.
Finding the exact minimum is computationally difficult in general: the original research establishes NP-hardness and develops approximation methods. A practical result should state whether it is exact, approximate or heuristic, together with the applicable assumptions.

Three practical examples

Knowledge exploration: An analyst seeks a compact connected view around selected concepts in a larger relationship graph, inspecting the additional concepts that link them.
Research navigation: A team explores how selected technical topics connect through an undirected association network. The links describe recorded relationships, not necessarily prerequisites or causes.
Network teaching: Students compare candidate connectors on a small graph to understand why minimizing all-pairs distance differs from minimizing the number of added nodes.

Think of it this way

Think of selecting a small set of stops that connects several required destinations. Short distances among the chosen stops are useful, but every extra stop becomes another place whose distance to the others must be counted. A seemingly helpful addition can therefore increase the total burden instead of reducing it.

Worked example

Consider an undirected, unweighted graph with query vertices A, B and C. It contains the path A - X - B - Y - C and another vertex Z connected directly to each query vertex. There is also a leaf T connected only to Z. Assume there are no other edges.
One candidate uses A, X, B, Y and C. Its induced subgraph is a five-vertex path. Among its ten unordered pairs, four are one edge apart, three are two apart, two are three apart and one is four apart. Its Wiener index is 4 × 1 + 3 × 2 + 2 × 3 + 1 × 4 = 20.
Another candidate uses A, B, C and Z. It is a three-leaf star. Three center-to-leaf distances are 1 and three leaf-to-leaf distances are 2, giving 3 + 6 = 9. This candidate is better under the objective.
Adding T creates a four-leaf star. Its index becomes 4 × 1 + 6 × 2 = 16. T shortens no existing route and adds distance contributions. These calculations compare specific feasible candidates; they are not an exhaustive optimality proof over every vertex subset.

Illustrative case study

Fictional learning platform Birch Atlas maintains an undirected graph linking related topics. Editors select several topics for a learning collection and ask an analyst to find a compact connecting view.
The analyst compares candidate subgraphs using the minimum-Wiener objective, then presents the included relationships for editorial review. A frequently connected general topic appears as a bridge, but editors discover that one of its links is too broad to be useful for this collection.
They revise the underlying relationship data and repeat the analysis. They do not treat the first connector as proof of an ideal learning sequence: undirected relatedness does not establish prerequisite order. This case is fictional.

Common misconceptions and mistakes

The objective counts every pair in the selected subgraph, including pairs involving added vertices. Restricting the sum to query pairs changes the problem.
Distances are measured inside the connector. Using full-graph distances can credit shortcuts that the selected subgraph does not contain.
The solution need not be a tree. Keeping existing edges among selected vertices can shorten distances without adding vertices.
A small Wiener index is not the same as the smallest average distance when candidate sizes differ. The objective is a sum, not a size-normalized average.
The graph's mathematical optimum is not automatically a causal, educational or operational optimum. It inherits the meaning and limitations of the input edges.

Business use

A Wiener connector can help explore relationships around a query set without displaying an entire large network. Its usefulness depends on whether short paths in the chosen graph correspond to relevant connections. Define the edge meaning, inspect added nodes and retain the optimization method's status in reports. Review the extracted view against domain knowledge before recommending actions.

Check your understanding

Why does the path candidate have ten pairs?

Answer: Five vertices produce 5 × 4 / 2 unordered pairs.

Why is the star's index 9?

Answer: Its three center - leaf pairs contribute 3 and three leaf pairs contribute 6.

Why must paths remain inside the selected subgraph?

Answer: Those are the distances defined by the connector objective.

Related terms

Graph
Shortest Paths
induced subgraph
shortest path
Wiener index
Steiner tree
query vertex
graph optimisation
approximation algorithm

Learn next

Enumerate the connected vertex subsets containing a query set in a tiny graph. Compute each induced subgraph's all-pairs distance sum and compare the best score with a minimum-edge connector.

Graph

Sources

Natali Ruchansky, Francesco Bonchi, David García-Soriano, Francesco Gullo and Nicolas Kourtellis, The Minimum Wiener Connector Problem, SIGMOD 2015. Author-hosted paper: https://www.cs.upc.edu/~dgarcia/pubs/the-minimum-wiener-connector-problem.pdf The path-and-star graph, calculations and Birch Atlas case are original illustrations. The entry follows the undirected, unweighted formulation and does not assume an extension to directed or weighted networks.

Previous: Widely applicable information criterion Next: Wiener filter