Community Structures

maximal_cliques(g)

Return a vector of vectors representing the node indices in each of the maximal cliques found in the undirected graph g.

julia> using Graphs
julia> g = SimpleGraph(3)
julia> add_edge!(g, 1, 2)
julia> add_edge!(g, 2, 3)
julia> maximal_cliques(g)
2-element Array{Array{Int64,N},1}:
 [2,3]
 [2,1]

global_clustering_coefficient(g)

Return the global clustering coefficient of graph g.

Examples

julia> using Graphs

julia> global_clustering_coefficient(star_graph(4))
0.0

julia> global_clustering_coefficient(smallgraph(:housex))
0.7894736842105263

local_clustering(g, v)
local_clustering(g, vs)

Return a tuple (a, b), where a is the number of triangles in the neighborhood of v and b is the maximum number of possible triangles. If a list of vertices vs is specified, return two vectors representing the number of triangles and the maximum number of possible triangles, respectively, for each node in the list.

This function is related to the local clustering coefficient r by $r=\frac{a}{b}$.

local_clustering_coefficient(g, v)
local_clustering_coefficient(g, vs)

Return the local clustering coefficient for node v in graph g. If a list of vertices vs is specified, return a vector of coefficients for each node in the list.

Examples

julia> using Graphs

julia> g = SimpleGraph(4);

julia> add_edge!(g, 1, 2);

julia> add_edge!(g, 2, 4);

julia> add_edge!(g, 4, 1);

julia> local_clustering_coefficient(g, [1, 2, 3])
3-element Array{Float64,1}:
 1.0
 1.0
 0.0

triangles(g[, v])
triangles(g, vs)

Return the number of triangles in the neighborhood of node v in graph g. If a list of vertices vs is specified, return a vector of number of triangles for each node in the list. If no vertices are specified, return the number of triangles for each node in the graph.

Examples

julia> using Graphs

julia> g = SimpleGraph(4);

julia> add_edge!(g, 1, 2);

julia> add_edge!(g, 2, 4);

julia> add_edge!(g, 4, 1);

julia> triangles(g)
4-element Array{Int64,1}:
 1
 1
 0
 1

core_periphery_deg(g)

Compute the degree-based core-periphery for graph g. Return the vertex assignments (1 for core and 2 for periphery) for each node in g.

References: Lip)

Examples

julia> using Graphs

julia> core_periphery_deg(star_graph(5))
5-element Array{Int64,1}:
 1
 2
 2
 2
 2

julia> core_periphery_deg(path_graph(3))
3-element Array{Int64,1}:
 2
 1
 2

label_propagation(g, maxiter=1000)

Community detection using the label propagation algorithm. Return two vectors: the first is the label number assigned to each node, and the second is the convergence history for each node. Will return after maxiter iterations if convergence has not completed.

References

• Raghavan et al.

modularity(g, c, distmx=weights(g), γ=1.0)

Return a value representing Newman's modularity Q for the undirected and directed graph g given the partitioning vector c. This method also supports weighted graphs if the distance matrix is provided.

Modularity $Q$ for undirected graph:

\[Q = \frac{1}{2m} \sum_{c} \left( e_{c} - \gamma \frac{K_c^2}{2m} \right)\]

Modularity $Q$ for directed graph:

\[Q = \frac{1}{m} \sum_{c} \left( e_{c} - \gamma \frac{K_c^{in} K_c^{out}}{m} \right)\]

where:

• $m$: total number of edges in the network
• $e_c$: number of edges in community $c$
• $K_c$: sum of the degrees of the nodes in community $c$ or the sum of the weighted degree of the nodes in community $c$ when the graph is weighted. $K_c^{in}$ sum of the in-degrees of the nodes in community $c$.

Optional Arguments

• distmx=weights(g): distance matrix for weighted graphs
• γ=1.0: where γ > 0 is a resolution parameter. When the modularity is used to find communities structure in networks (i.e with Louvain's method for community detection), higher resolutions lead to more communities, while lower resolutions lead to fewer communities. Where γ=1.0 it lead to the traditional definition of the modularity.

References

• M. E. J. Newman and M. Girvan. "Finding and evaluating community structure in networks". Phys. Rev. E 69, 026113 (2004). (arXiv)
• J. Reichardt and S. Bornholdt. "Statistical mechanics of community detection". Phys. Rev. E 74, 016110 (2006). (arXiv)
• E. A. Leicht and M. E. J. Newman. "Community structure in directed networks". Physical Review Letter, 100:118703, (2008). (arXiv)

Examples

julia> using Graphs

julia> barbell = blockdiag(complete_graph(3), complete_graph(3));

julia> add_edge!(barbell, 1, 4);

julia> modularity(barbell, [1, 1, 1, 2, 2, 2])
0.35714285714285715

julia> modularity(barbell, [1, 1, 1, 2, 2, 2], γ=0.5)
0.6071428571428571  

julia> using SimpleWeightedGraphs

julia> triangle = SimpleWeightedGraph(3);

julia> add_edge!(triangle, 1, 2, 1);

julia> add_edge!(triangle, 2, 3, 1);

julia> add_edge!(triangle, 3, 1, 1);

julia> barbell = blockdiag(triangle, triangle);

julia> add_edge!(barbell, 1, 4, 5); # this edge has a weight of 5

julia> modularity(barbell, [1, 1, 1, 2, 2, 2])
0.045454545454545456

assortativity(g)

Return the assortativity coefficient of graph g, defined as the Pearson correlation of excess degree between the end vertices of all the edges of the graph.

The excess degree is equal to the degree of linked vertices minus one, i.e. discounting the edge that links the pair. In directed graphs, the paired values are the out-degree of source vertices and the in-degree of destination vertices.

Examples

julia> using Graphs

julia> assortativity(star_graph(4))
-1.0