Community Structures

Erdos.jl contains many algorithm to detect and analyze community structures in graphs.

# Erdos.global_clustering_coefficient — Method.

global_clustering_coefficient(g)

Computes the global clustering coefficient.

source

# Erdos.local_clustering — Function.

local_clustering(g, vlist = vertices(g))

Returns two vectors, respectively containing the first and second result of local_clustering_coefficients(g, v) for each v in vlist.

source

# Erdos.local_clustering — Method.

local_clustering(g, v)

Returns 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. It is related to the local clustering coefficient by r=a/b.

source

# Erdos.local_clustering_coefficient — Function.

local_clustering_coefficient(g, vlist = vertices(g))

Returns a vector containing the local clustering coefficients for vertices vlist.

source

# Erdos.local_clustering_coefficient — Method.

local_clustering_coefficient(g, v)

Computes the local clustering coefficient for node v.

source

# Erdos.triangles — Function.

triangles(g, vlist = vertices(g))

Returns a vector containing the number of triangles for vertices vlist.

source

# Erdos.triangles — Method.

triangles(g, v)

Returns the number of triangles in the neighborhood for node v.

source

# Erdos.core_periphery_deg — Method.

core_periphery_deg(g)

A simple degree-based core-periphery detection algorithm (see Lip). Returns the vertex assignments (1 for core and 2 for periphery).

source

# Erdos.modularity — Method.

modularity(g, c)

Computes Newman's modularity Q for graph g given the partitioning c.

source

# Erdos.maximal_cliques — Method.

Finds all maximal cliques of an undirected graph.

julia> using Erdos
julia> g = Graph(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

# Erdos.community_detection_bethe — Function.

community_detection_bethe(g::AGraph, k=-1; kmax=15)

Community detection using the spectral properties of the Bethe Hessian matrix associated to g (see Saade et al.). k is the number of communities to detect. If omitted or if k < 1 the optimal number of communities will be automatically selected. In this case the maximum number of detectable communities is given by kmax. Returns a vector containing the vertex assignments.

source

# Erdos.community_detection_nback — Method.

community_detection_nback(g, k)

Community detection using the spectral properties of the non-backtracking matrix of graph g (see Krzakala et al.). k is the number of communities to detect.

See also community_detection_bethe for a related community ddetection algorithm.

Returns a vector with the vertex assignments in the communities.

source

# Erdos.label_propagation — Method.

label_propagation(g; maxiter=1000)

Community detection using the label propagation algorithm (see Raghavan et al.). g is the input Graph, maxiter is the maximum number of iterations. Returns a vertex assignments and the convergence history

source

# Erdos.nonbacktrack_embedding — Method.

nonbacktrack_embedding(g::AGraph, k::Int)

Spectral embedding of the non-backtracking matrix of g (see Krzakala et al.).

`g`: imput Graph
`k`: number of dimensions in which to embed

Returns a matrix ϕ where ϕ[:,i] are the coordinates for vertex i.

Note: does not explicitly construct the nonbacktracking_matrix. See Nonbacktracking for details.

source