Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

How do I find all vertices in a graph with maximum degree?

Given a graph, say

g = Graph[{x -> a, y -> c, a -> b,
           b -> c, a -> c, d -> c,
           a -> d, b -> d},
      VertexLabels -> "Name"] 

g

How do I find all vertices in a graph with the maximum degree i.e. a list of all vertices that has the most number of edges, and highlight them in the graph?

In this case, it would be the vertices {a,c}.

like image 644
Prashant Bhate Avatar asked Jan 16 '12 00:01

Prashant Bhate


2 Answers

Here's an approach using DegreeCentrality:

(* In[41]:= *) max = Pick[VertexList[g], DegreeCentrality[g], Max[DegreeCentrality[g]]]

(* Out[41]= *) {a, c}

(* In[42]:= *) HighlightGraph[g, max]

enter image description here

like image 141
Brett Champion Avatar answered Sep 23 '22 10:09

Brett Champion


You can generally highlight vertices by their degree:

    HighlightGraph[g, 
 Table[Style[VertexList[g][[i]], 
   ColorData["TemperatureMap"][
    VertexDegree[g][[i]]/Max[VertexDegree[g]]]], {i, VertexCount[g]}]]

enter image description here

like image 36
Vitaliy Kaurov Avatar answered Sep 21 '22 10:09

Vitaliy Kaurov