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?
2 Answers
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
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]]
-
$\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$ 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$ 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$ 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$ 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]
.
Sort
you will lose the whole meaning ofVertexDegree
: the $i^{th}$ value returned byVertexDegree
corresponds to the $i^{th}$ vertex.VertexDegree
will only tell you the number of connections each vertex have. $\endgroup$Subgraph
andSort
them in terms of whatSort@VertexDegree@G
would yield? $\endgroup$