Sign up ×
Mathematica Stack Exchange is a question and answer site for users of Mathematica. It's 100% free, no registration required.

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?

share|improve this question
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

2 Answers 2

up vote 2 down vote accepted

First let's take a RandomGraph:

g = RandomGraph[BarabasiAlbertGraphDistribution[10, 2], VertexLabels -> "Name",
                  ImagePadding -> 20]
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:


enter image description here

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


enter image description here

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]]

enter image description here

share|improve this answer
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].

share|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.