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$
$\endgroup$
4
2 Answers
$\begingroup$
$\endgroup$
9
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
Graphout 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
$\begingroup$
$\endgroup$
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].
answered Sep 17, 2015 at 8:09
Sortyou will lose the whole meaning ofVertexDegree: the $i^{th}$ value returned byVertexDegreecorresponds to the $i^{th}$ vertex.VertexDegreewill only tell you the number of connections each vertex have. $\endgroup$SubgraphandSortthem in terms of whatSort@VertexDegree@Gwould yield? $\endgroup$