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?

  • $\begingroup$ 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. $\endgroup$
    – Öskå
    Apr 17, 2014 at 9:57
  • $\begingroup$ @Ö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? $\endgroup$
    – user13772
    Apr 17, 2014 at 9:59
  • $\begingroup$ You want to extract each Subgraph and Sort them in terms of what Sort@VertexDegree@G would yield? $\endgroup$
    – Öskå
    Apr 17, 2014 at 10:02
  • $\begingroup$ @Ö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. $\endgroup$
    – user13772
    Apr 17, 2014 at 10:17

2 Answers 2


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

  • $\begingroup$ 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]]? $\endgroup$
    – user13772
    Apr 17, 2014 at 11:02
  • $\begingroup$ 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. $\endgroup$
    – user13772
    Apr 17, 2014 at 12:00
  • $\begingroup$ So.., you want to make a Graph out of the shared vertices/edges of the first $n^{th}$ verticies? $\endgroup$
    – Öskå
    Apr 17, 2014 at 12:21
  • $\begingroup$ 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. $\endgroup$
    – Öskå
    Apr 17, 2014 at 13:11
  • $\begingroup$ 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. $\endgroup$
    – user13772
    Apr 17, 2014 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].


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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