Community Structures

# Community Structures

LightGraphs.jl contains many algorithm to detect and analyze community structures in graphs. These include:

## Full Docs

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 LightGraphs
julia> g = SimpleGraph(3)
julia> maximal_cliques(g)
2-element Array{Array{Int64,N},1}:
[2,3]
[2,1]
source
global_clustering_coefficient(g)

Return the global clustering coefficient of graph g.

Examples

julia> using LightGraphs

julia> global_clustering_coefficient(star_graph(4))
0.0

julia> global_clustering_coefficient(smallgraph(:housex))
0.7894736842105263
source
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}$.

source
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 LightGraphs

julia> g = SimpleGraph(4);

julia> local_clustering_coefficient(g, [1, 2, 3])
3-element Array{Float64,1}:
1.0
1.0
0.0
source
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 LightGraphs

julia> g = SimpleGraph(4);

julia> triangles(g)
4-element Array{Int64,1}:
1
1
0
1
source
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 LightGraphs

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
source
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

source
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 LightGraphs

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

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);

0.045454545454545456