Community structures

Graphs.jl contains several algorithms to detect and analyze community structures.

Index

Full docs

Graphs.assortativityMethod
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
source
Graphs.clique_percolationFunction
clique_percolation(g, k=3)

Community detection using the clique percolation algorithm. Communities are potentionally overlapping. Return a vector of vectors c such that c[i] is the set of vertices in community i. The parameter k defines the size of the clique to use in percolation.

References

Examples

julia> using Graphs

julia> clique_percolation(clique_graph(3, 2))
2-element Array{BitSet,1}:
 BitSet([4, 5, 6])
 BitSet([1, 2, 3])

julia> clique_percolation(clique_graph(3, 2), k=2)
1-element Array{BitSet,1}:
 BitSet([1, 2, 3, 4, 5, 6])

julia> clique_percolation(clique_graph(3, 2), k=4)
0-element Array{BitSet,1}
source
Graphs.maximal_cliquesFunction
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]
source
Graphs.local_clusteringMethod
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
Graphs.local_clustering_coefficientMethod
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
source
Graphs.trianglesMethod
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
source
Graphs.core_periphery_degFunction
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
source
Graphs.label_propagationMethod
label_propagation(g, maxiter=1000; rng=nothing, seed=nothing)

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
Graphs.vote!Method
vote!(rng, g, m, c, u)

Return the label with greatest frequency.

source
Graphs.modularityMethod
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
source