({{, (RefLink[FindGraphCommunities, paclet:ref/FindGraphCommunities])[g] 
finds communities in the graph g.}, {, (RefLink[FindGraphCommunities, paclet:ref/FindGraphCommunities])[{v->w,…}]
uses rules v->w to specify the graph g.}})

OpenersNotesSection(Spacer1)Details and Options

(RefLink[FindGraphCommunities, paclet:ref/FindGraphCommunities]) finds communities with many edges joining vertices of the same community and comparatively few edges joining vertices of different communities.

(RefLink[FindGraphCommunities, paclet:ref/FindGraphCommunities]) returns a list of communities {(Subscript[c, 1]),(Subscript[c, 2]),…}, where each community (Subscript[c, i]) is a list of vertices.

The communities are ordered by their length, with the largest community first.

(RefLink[FindGraphCommunities, paclet:ref/FindGraphCommunities]) supports a (RefLink[Method, paclet:ref/Method]) option that specifies the detailed method to use.

Possible settings for the (RefLink[Method, paclet:ref/Method]) option include:

(RefLink[FindGraphCommunities, paclet:ref/FindGraphCommunities]) works with undirected graphs, directed graphs, weighted graphs, multigraphs, and mixed graphs.

OpenersPrimaryExamplesSection(Spacer1)Examples  (22)

OpenersExampleSection0(Spacer1)Basic Examples  (2)

Find communities in a graph:

g=Graph[{1\[UndirectedEdge]2,2\[UndirectedEdge]3,1\[UndirectedEdge]3,3\[UndirectedEdge]4,4\[UndirectedEdge]5,7\[UndirectedEdge]6,8\[UndirectedEdge]6,5\[UndirectedEdge]7,7\[UndirectedEdge]8}]

FindGraphCommunities[g]

Highlight the communities:

HighlightGraph[g,Map[Subgraph[g,#]&, %]]

Visualize communities:

RandomGraph[WattsStrogatzGraphDistribution[30,0.3,3]]

CommunityGraphPlot[%,FindGraphCommunities[%]]

OpenersExampleSection1(Spacer1)Scope  (7)

(RefLink[FindGraphCommunities, paclet:ref/FindGraphCommunities]) works with undirected graphs:

FindGraphCommunities[]

Directed graphs:

FindGraphCommunities[]

Weighted graphs:

FindGraphCommunities[]

Multigraphs:

FindGraphCommunities[]

Mixed graphs:

FindGraphCommunities[]

Use rules to specify the graph:

FindGraphCommunities[{1->2,1->3,2->4,3->4,3->5,4->6,5->6,5->7,6->8,7->8}]

(RefLink[FindGraphCommunities, paclet:ref/FindGraphCommunities]) works with large graphs:

g=RandomGraph[WattsStrogatzGraphDistribution[10^4,0.25,5]];

Timing[Length[FindGraphCommunities[g]]]

OpenersExampleSection2(Spacer1)Options  (6)

OpenersExampleSubsection0(Spacer1)Method  (6)

By default, (RefLink[FindGraphCommunities, paclet:ref/FindGraphCommunities]) uses modularity maximization methods:

FindGraphCommunities[]

This can also be obtained with (RefLink[Method, paclet:ref/Method])->"Modularity":

FindGraphCommunities[,Method->"Modularity"]

Use (RefLink[Method, paclet:ref/Method])->"Hierarchical" for hierarchical clustering based on vertex similarity:

FindGraphCommunities[,Method->"Hierarchical"]

Use (RefLink[Method, paclet:ref/Method])->"Spectral" for spectral partitioning:

FindGraphCommunities[,Method->"Spectral"]

Use (RefLink[Method, paclet:ref/Method])->"Centrality" for partitioning based on edge centrality:

FindGraphCommunities[,Method->"Centrality"]

Use (RefLink[Method, paclet:ref/Method])->"CliquePercolation" for k-clique percolation:

FindGraphCommunities[,Method->"CliquePercolation"]

Use (RefLink[Method, paclet:ref/Method])->"VertexMoving" to improve the result obtained by default:

g=GridGraph[{3,7}]

N[GraphAssortativity[g,FindGraphCommunities[g]]]

N[GraphAssortativity[g,FindGraphCommunities[g,Method->"VertexMoving"]]]

OpenersExampleSection3(Spacer1)Applications  (2)

Find communities in a friendship network between members of a karate club:

g=ExampleData[{"NetworkGraph","ZacharyKarateClub"}];

FindGraphCommunities[g,Method->"Hierarchical"]

Predict the split of the network in case of an internal conflict:

HighlightGraph[g,Subgraph[g,#]&/@%,GraphHighlightStyle->"DehighlightHide"]

A weighted network of wins in the National Hockey League during regular season 2010–2011. Group teams by conferences:

g=ExampleData[{"NetworkGraph","NationalHockeyLeague"}];

conferences=FindGraphCommunities[g]

Partition teams in six divisions:

divisions=FindGraphPartition[g,6]

OpenersExampleSection4(Spacer1)Properties & Relations  (5)

Communities are ordered by their length, with the largest community first:

g=RandomGraph[SpatialGraphDistribution[100,0.15]];

Length/@FindGraphCommunities[g]

By default, (RefLink[FindGraphCommunities, paclet:ref/FindGraphCommunities]) gives communities with high modularity:

g=ExampleData[{"NetworkGraph","ZacharyKarateClub"}];

FindGraphCommunities[g]

Use (RefLink[GraphAssortativity, paclet:ref/GraphAssortativity]) to compute the modularity:

N[GraphAssortativity[g,%,"Normalized"-> False]]

Use (RefLink[FindGraphPartition, paclet:ref/FindGraphPartition]) to find partitions of vertices into k parts of approximately equal size:

g=RandomGraph[WattsStrogatzGraphDistribution[20,0.1,3]];

FindGraphPartition[g,3]

The size of communities in the Watts–Strogatz model:

𝒟[p_]:=GraphPropertyDistribution[Length[FindGraphCommunities[g]],g\[Distributed]WattsStrogatzGraphDistribution[1000,p]]

ListPlot[Table[{p,RandomVariate[𝒟[p]]},{p,0,1,0.01}]]

In random spatial graphs:

𝒟[r_]:=GraphPropertyDistribution[Length[FindGraphCommunities[g]],g\[Distributed]SpatialGraphDistribution[100,r]]

ListPlot[Table[{r,RandomVariate[𝒟[r]]},{r,0,0.25,0.001}]]

(RefLink[CommunityGraphPlot, paclet:ref/CommunityGraphPlot]) finds and visualizes communities:

g=RandomGraph[WattsStrogatzGraphDistribution[30,0.3,3]];

CommunityGraphPlot[g]

Specify communities:

CommunityGraphPlot[g,FindGraphCommunities[g,Method->"Spectral"]]

({{DocumentationFooterIconsRelatedFunction.png, ({{See Also}, {(RefLink[FindGraphPartition, paclet:ref/FindGraphPartition])  ▪  (RefLink[GraphAssortativity, paclet:ref/GraphAssortativity])  ▪  (RefLink[FindClusters, paclet:ref/FindClusters])}})}})

({{DocumentationFooterIconsRelatedGuide.png, ({{Related Guides}, {▪(RefLinkPlain[Social Network Analysis, paclet:guide/SocialNetworks])}, {▪(RefLinkPlain[Cluster Analysis, paclet:guide/ClusterAnalysis])}, {▪(RefLinkPlain[Scientific Data Analysis, paclet:guide/ScientificDataAnalysis])}, {▪(RefLinkPlain[Machine Learning, paclet:guide/MachineLearning])}})}})