How do I use Subgraph to sample the $n$ vertices of a graph with the greatest connectivity?

Let $G$ be an arbitrary graph with some number of vertices $||V||$ and some number of edges $||E||$. We can use Subgraph to generate, well, a subgraph of G with the vertices we desire. However, how can I use the patt option for Subgraph (or any method) to grab the set of n vertices with the greatest degree in $G$? In other words, if we make a list Sort[VertexDegree[G]], how can we select vertices for the subgraph starting from the right-hand-side of the output list then working our way to the left?

• By using Sort you will lose the whole meaning of VertexDegree: the $i^{th}$ value returned by VertexDegree corresponds to the $i^{th}$ vertex. VertexDegree will only tell you the number of connections each vertex have. – Öskå Apr 17 '14 at 9:57
• @Öskå I just meant to use Sort to illustrate what I was trying to do do. I'd like to use something like Select I suppose? – user13772 Apr 17 '14 at 9:59
• You want to extract each Subgraph and Sort them in terms of what Sort@VertexDegree@G would yield? – Öskå Apr 17 '14 at 10:02
• @Öskå Oh, I meant that I would like to generate subgraph consisting of the vertices with the greatest possible connectivity in the larger graph we're pulling the subgraph from. – user13772 Apr 17 '14 at 10:17

First let's take a RandomGraph:

SeedRandom@1;
g = RandomGraph[BarabasiAlbertGraphDistribution[10, 2], VertexLabels -> "Name",
list = Reverse@SortBy[
Thread[{Range@VertexCount@g, VertexDegree[g]}], Last@# &]
(*{vi, vertexdegree@i}*)
{{1, 7}, {2, 6}, {6, 5}, {4, 4}, {10, 2}, {9, 2}, {8, 2}, {7, 2}, {5, 2}, {3, 2}}

meaning that the vertex 1 has 7 neighbours, 2 has 6 and so on.

Then you can define the following function:

highlightSubgraph[list_] := HighlightGraph[g, Style[Subgraph[g, # <-> _],
Hue[#/VertexCount@g]], VertexLabelStyle -> {# -> {Red, Bold, 16}}, PlotLabel -> {#, #2}]
& @@@ list;

and plot every Subgraph:

highlightSubgraph@list or plot only the first $n^{th}$:

highlightSubgraph@list[[1;;3]] If you want to use a threshold you can of course highlightSubgraph@Select[list, Last@# > n &]

If you only want the Subgraph the following will do:

Subgraph[g, # <-> _, PlotLabel -> {#, #2}] & @@@ list[[1 ;; 3]] • Wait, why do the subgraphs have more than the three vertices? I'm looking for the subgraph (connected or not) composed of only the vertices from the output of list[[1;;3]]? – user13772 Apr 17 '14 at 11:02
• Say we have a graph with five vertices connected in linear order (v1 <--> v2 <--> v3 <--> v4 <--> v5). We then select vertices {v1, v2, v4} (in a more complex example, these would be the vertices with highest order). Finally, we make the subgraph: {v1 <--> v2, v4 unconnected}. Does this make sense? We just want to grab the 'n' highest order vertices, and then grab all the edges these higher order vertices share with one-another, and draw a "subgraph" with just these grabbed vertices and edges. – user13772 Apr 17 '14 at 12:00
• So.., you want to make a Graph out of the shared vertices/edges of the first $n^{th}$ verticies? – Öskå Apr 17 '14 at 12:21
• One of the issue is that in the Graph I took I have no shared vertices between the 3 vertices with the greatest connectivity. See here. – Öskå Apr 17 '14 at 13:11
• Can we just delete any unconnected vertices, or if possible, keep grabbing vertices in the order of their connectivity in the larger graph until we have a subgraph of the desired size? The latter suggestion sounds maybe too hard, so I'd be fine with just deleting unconnected vertices. – user13772 Apr 17 '14 at 13:19

This question is not really about graphs, but about how to select n elements from list A so that the corresponding numbers in list B are the largest.

The best way is Ordering, not Sort or SortBy.

Suppose your graph is g. Then the indices of the n largest elements of VertexDegree[g] are

indices = Ordering[VertexDegree[g], -n]

Then just take vertices = VertexList[g][[ indices ]];, and finally Subgraph[g, vertices].