Take the 2-minute tour ×
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 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 at 9:59
    
You want to extract each Subgraph and Sort them in terms of what Sort@VertexDegree@G would yield? –  Öskå Apr 17 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 at 10:17

1 Answer 1

up vote 2 down vote accepted

First let's take a RandomGraph:

SeedRandom@1;
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:

highlightSubgraph@list

enter image description here

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

highlightSubgraph@list[[1;;3]]

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 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 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 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 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 at 13:19

Your Answer

 
discard

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.