Community structures

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

clique_percolation(g, k=3)

Community detection using the clique percolation algorithm. Communities are potentially 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

• Palla G, Derenyi I, Farkas I J, et al.

Examples

julia> using Graphs

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

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

julia> clique_percolation(clique_graph(3, 2), k=4)
BitSet[]

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)
{3, 0} undirected simple Int64 graph

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

julia> add_edge!(g, 2, 3)
true

julia> maximal_cliques(g)
2-element Vector{Vector{Int64}}:
 [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 Vector{Float64}:
 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 Vector{Int64}:
 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 Vector{Int64}:
 1
 2
 2
 2
 2

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

NeighComm{T}

Type to record neighbor labels and their counts.

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

• Raghavan et al.

range_shuffle!(rng, r, a)

Fast shuffle Array a in UnitRange r.

vote!(rng, g, m, c, u)

Return the label with greatest frequency.

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 Graphs

julia> triangle = cycle_graph(3);

julia> barbell = blockdiag(triangle, triangle);

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

julia> distmx = Matrix(weights(barbell));

julia> distmx[1, 4] = distmx[4, 1] = 5;  # additional edge has a weight of 5

julia> round(modularity(barbell, [1, 1, 1, 2, 2, 2]; distmx), digits=6)
0.045455

rich_club(g, k)

Return the non-normalised rich-club coefficient of graph g, with degree cut-off k.

julia> using Graphs

julia> g = star_graph(5)
{5, 4} undirected simple Int64 graph

julia> rich_club(g, 1)
0.4