## Documentation ¶

### Overview ¶

Package community provides graph community detection functions.

### Constants ¶

This section is empty.

### Variables ¶

This section is empty.

### Functions ¶

#### func KCliqueCommunities ¶

func KCliqueCommunities(k int, g graph.Undirected) [][]graph.Node

KCliqueCommunities returns the k-clique communties of the undirected graph g for k greater than zero. The returned communities are identified by linkage via k-clique adjacency, where adjacency is defined as having k-1 common nodes. KCliqueCommunities returns a single component including the full set of nodes of g when k is 1, and the classical connected components of g when k is 2. Note that k-clique communities may contain common nodes from g.

k-clique communities are described in Palla et al. doi:10.1038/nature03607.

#### func ModularMultiplexScore ¶

func ModularMultiplexScore(g Multiplex, weights []float64, all bool, score func(ReducedMultiplex) float64, effort int, src rand.Source) func(float64) (float64, Reduced)

ModularMultiplexScore returns a modularized scoring function for Profile based on the graph g and the given score function. The effort parameter determines how many attempts will be made to get an improved score for any given resolution.

#### func ModularScore ¶

func ModularScore(g graph.Graph, score func(ReducedGraph) float64, effort int, src rand.Source) func(float64) (float64, Reduced)

ModularScore returns a modularized scoring function for Profile based on the graph g and the given score function. The effort parameter determines how many attempts will be made to get an improved score for any given resolution.

#### func Q ¶

func Q(g graph.Graph, communities [][]graph.Node, resolution float64) float64

Q returns the modularity Q score of the graph g subdivided into the given communities at the given resolution. If communities is nil, the unclustered modularity score is returned. The resolution parameter is γ as defined in Reichardt and Bornholdt doi:10.1103/PhysRevE.74.016110. Q will panic if g has any edge with negative edge weight.

If g is undirected, Q is calculated according to

Q = 1/2m \sum_{ij} [ A_{ij} - (\gamma k_i k_j)/2m ] \delta(c_i,c_j),


If g is directed, it is calculated according to

Q = 1/m \sum_{ij} [ A_{ij} - (\gamma k_i^in k_j^out)/m ] \delta(c_i,c_j).


graph.Undirect may be used as a shim to allow calculation of Q for directed graphs with the undirected modularity function.

#### func QMultiplex ¶

func QMultiplex(g Multiplex, communities [][]graph.Node, weights, resolutions []float64) []float64

QMultiplex returns the modularity Q score of the multiplex graph layers subdivided into the given communities at the given resolutions and weights. Q is returned as the vector of weighted Q scores for each layer of the multiplex graph. If communities is nil, the unclustered modularity score is returned. If weights is nil layers are equally weighted, otherwise the length of weights must equal the number of layers. If resolutions is nil, a resolution of 1.0 is used for all layers, otherwise either a single element slice may be used to specify a global resolution, or the length of resolutions must equal the number of layers. The resolution parameter is γ as defined in Reichardt and Bornholdt doi:10.1103/PhysRevE.74.016110. QMultiplex will panic if the graph has any layer weight-scaled edge with negative edge weight.

If g is undirected, Q is calculated according to

Q_{layer} = w_{layer} \sum_{ij} [ A_{layer}*_{ij} - (\gamma_{layer} k_i k_j)/2m_{layer} ] \delta(c_i,c_j),


If g is directed, it is calculated according to

Q_{layer} = w_{layer} \sum_{ij} [ A_{layer}*_{ij} - (\gamma_{layer} k_i^in k_j^out)/m_{layer} ] \delta(c_i,c_j).


Note that Q values for multiplex graphs are not scaled by the total layer edge weight.

graph.Undirect may be used as a shim to allow calculation of Q for directed graphs.

#### func Size ¶

func Size(g ReducedGraph) float64

Size is a score function that is the reciprocal of the number of communities.

#### func SizeMultiplex ¶

func SizeMultiplex(g ReducedMultiplex) float64

SizeMultiplex is a score function that is the reciprocal of the number of communities.

#### func Weight ¶

func Weight(g ReducedGraph) float64

Weight is a score function that is the sum of community weights. The concrete type of g must be a pointer to a ReducedUndirected or a ReducedDirected, otherwise Weight will panic.

#### func WeightMultiplex ¶

func WeightMultiplex(g ReducedMultiplex) float64

WeightMultiplex is a score function that is the sum of community weights. The concrete type of g must be pointer to a ReducedUndirectedMultiplex or a ReducedDirectedMultiplex, otherwise WeightMultiplex will panic.

### Types ¶

#### type DirectedLayers ¶

type DirectedLayers []graph.Directed

DirectedLayers implements DirectedMultiplex.

#### func NewDirectedLayers ¶

func NewDirectedLayers(layers ...graph.Directed) (DirectedLayers, error)

NewDirectedLayers returns a DirectedLayers using the provided layers ensuring there is a match between IDs for each layer.

#### func (DirectedLayers) Depth ¶

func (g DirectedLayers) Depth() int

Depth returns the depth of the multiplex graph.

#### func (DirectedLayers) Layer ¶

func (g DirectedLayers) Layer(l int) graph.Directed

Layer returns the lth layer of the multiplex graph.

#### func (DirectedLayers) Nodes ¶

func (g DirectedLayers) Nodes() graph.Nodes

Nodes returns the nodes of the receiver.

#### type DirectedMultiplex ¶

type DirectedMultiplex interface {
Multiplex

// Layer returns the lth layer of the
// multiplex graph.
Layer(l int) graph.Directed
}

DirectedMultiplex is a directed multiplex graph.

#### type Interval ¶

type Interval struct {
// Low and High delimit the interval
// such that the interval is [low, high).
Low, High float64

// Score is the score of the interval.
Score float64

// Reduced is the best scoring
// community membership found for the
// interval.
Reduced
}

Interval is an interval of resolutions with a common score.

#### func Profile ¶

func Profile(fn func(float64) (float64, Reduced), log bool, grain, low, high float64) (profile []Interval, err error)

Profile returns an approximate profile of score values in the resolution domain [low,high) at the given granularity. The score is calculated by bisecting calls to fn. If log is true, log space bisection is used, otherwise bisection is linear. The function fn should be monotonically decreasing in at least 1/grain evaluations. Profile will attempt to detect non-monotonicity during the bisection.

Since exact modularity optimization is known to be NP-hard and Profile calls modularization routines repeatedly, it is unlikely to return the exact resolution profile.

Example (Multiplex)
Output:

Low:0.1 High:0.72 Score:26 Communities:[ [1 7 9 12] [2 8 11] [3 4 5 10] ] Q=[24.7 1.97]
Low:0.72 High:1.1 Score:24 Communities:[[0 6] [1 7 9 12] [2 8 11] [3 4 5 10]] Q=[16.9 14.1]
Low:1.1 High:1.2 Score:18 Communities:[[0 2 6 11] [1 7 9 12] [3 4 5 8 10]] Q=[9.16 25.1]
Low:1.2 High:1.6 Score:10 Communities:[[0 3 4 5 6 10] [1 7 9 12] [2 8 11]] Q=[10.5 26.7]
Low:1.6 High:1.6 Score:8 Communities:[[0 1 6 7 9 12] [2 8 11] [3 4 5 10]] Q=[5.56 39.8]
Low:1.6 High:1.8 Score:2 Communities:[[0 2 3 4 5 6 10] [1 7 8 9 11 12]] Q=[-1.82 48.6]
Low:1.8 High:2.3 Score:-6 Communities:[[0 2 3 4 5 6 8 10 11] [1 7 9 12]] Q=[-5 57.5]
Low:2.3 High:2.4 Score:-10 Communities:[[0 1 2 6 7 8 9 11 12] [3 4 5 10]] Q=[-11.2 79]
Low:2.4 High:4.3 Score:-52 Communities:[[0 1 2 3 4 5 6 7 8 9 10 11 12]] Q=[-46.1 117]
Low:4.3 High:10 Score:-54 Communities:[[0 1 2 3 4 6 7 8 9 10 11 12] ] Q=[-82 254]

Example (Simple)
Output:

Low:0.1 High:0.29 Score:14 Communities:[[0 1 2 3 4 5]] Q=0.9
Low:0.29 High:2.3 Score:12 Communities:[[0 1 2] [3 4 5]] Q=0.714
Low:2.3 High:3.5 Score:4 Communities:[[0 1]   [4 5]] Q=-0.31
Low:3.5 High:10 Score:0 Communities:[     ] Q=-0.607


#### type Multiplex ¶

type Multiplex interface {
// Nodes returns the nodes
// for the multiplex graph.
// All layers must refer to the same
// set of nodes.
Nodes() graph.Nodes

// Depth returns the number of layers
// in the multiplex graph.
Depth() int
}

Multiplex is a multiplex graph.

#### type Reduced ¶

type Reduced interface {
// Communities returns the community
// structure of the reduction.
Communities() [][]graph.Node
}

Reduced is a graph reduction.

#### type ReducedDirected ¶

type ReducedDirected struct {
// contains filtered or unexported fields
}

ReducedDirected is a directed graph of communities derived from a parent graph by reduction.

#### func (*ReducedDirected) Communities ¶

func (g *ReducedDirected) Communities() [][]graph.Node

Communities returns the community memberships of the nodes in the graph used to generate the reduced graph.

#### func (*ReducedDirected) Edge ¶

func (g *ReducedDirected) Edge(uid, vid int64) graph.Edge

Edge returns the edge from u to v if such an edge exists and nil otherwise. The node v must be directly reachable from u as defined by the From method.

#### func (*ReducedDirected) Expanded ¶

func (g *ReducedDirected) Expanded() ReducedGraph

Expanded returns the next lower level of the module clustering or nil if at the lowest level.

#### func (*ReducedDirected) From ¶

func (g *ReducedDirected) From(uid int64) graph.Nodes

From returns all nodes in g that can be reached directly from u.

#### func (*ReducedDirected) HasEdgeBetween ¶

func (g *ReducedDirected) HasEdgeBetween(xid, yid int64) bool

HasEdgeBetween returns whether an edge exists between nodes x and y.

#### func (*ReducedDirected) HasEdgeFromTo ¶

func (g *ReducedDirected) HasEdgeFromTo(uid, vid int64) bool

HasEdgeFromTo returns whether an edge exists from node u to v.

#### func (*ReducedDirected) Node ¶

func (g *ReducedDirected) Node(id int64) graph.Node

Node returns the node with the given ID if it exists in the graph, and nil otherwise.

#### func (*ReducedDirected) Nodes ¶

func (g *ReducedDirected) Nodes() graph.Nodes

Nodes returns all the nodes in the graph.

#### func (*ReducedDirected) Structure ¶

func (g *ReducedDirected) Structure() [][]graph.Node

Structure returns the community structure of the current level of the module clustering. The first index of the returned value corresponds to the index of the nodes in the next higher level if it exists. The returned value should not be mutated.

#### func (*ReducedDirected) To ¶

func (g *ReducedDirected) To(vid int64) graph.Nodes

To returns all nodes in g that can reach directly to v.

#### func (*ReducedDirected) Weight ¶

func (g *ReducedDirected) Weight(xid, yid int64) (w float64, ok bool)

Weight returns the weight for the edge between x and y if Edge(x, y) returns a non-nil Edge. If x and y are the same node the internal node weight is returned. If there is no joining edge between the two nodes the weight value returned is zero. Weight returns true if an edge exists between x and y or if x and y have the same ID, false otherwise.

#### func (*ReducedDirected) WeightedEdge ¶

func (g *ReducedDirected) WeightedEdge(uid, vid int64) graph.WeightedEdge

WeightedEdge returns the weighted edge from u to v if such an edge exists and nil otherwise. The node v must be directly reachable from u as defined by the From method.

#### type ReducedDirectedMultiplex ¶

type ReducedDirectedMultiplex struct {
// contains filtered or unexported fields
}

ReducedDirectedMultiplex is a directed graph of communities derived from a parent graph by reduction.

#### func (*ReducedDirectedMultiplex) Communities ¶

func (g *ReducedDirectedMultiplex) Communities() [][]graph.Node

Communities returns the community memberships of the nodes in the graph used to generate the reduced graph.

#### func (*ReducedDirectedMultiplex) Depth ¶

func (g *ReducedDirectedMultiplex) Depth() int

Depth returns the number of layers in the multiplex graph.

#### func (*ReducedDirectedMultiplex) Expanded ¶

func (g *ReducedDirectedMultiplex) Expanded() ReducedMultiplex

Expanded returns the next lower level of the module clustering or nil if at the lowest level.

#### func (*ReducedDirectedMultiplex) Layer ¶

func (g *ReducedDirectedMultiplex) Layer(l int) graph.Directed

Layer returns the lth layer of the multiplex graph.

#### func (*ReducedDirectedMultiplex) Nodes ¶

func (g *ReducedDirectedMultiplex) Nodes() graph.Nodes

Nodes returns all the nodes in the graph.

#### func (*ReducedDirectedMultiplex) Structure ¶

func (g *ReducedDirectedMultiplex) Structure() [][]graph.Node

Structure returns the community structure of the current level of the module clustering. The first index of the returned value corresponds to the index of the nodes in the next higher level if it exists. The returned value should not be mutated.

#### type ReducedGraph ¶

type ReducedGraph interface {
graph.Graph

// Communities returns the community memberships
// of the nodes in the graph used to generate
// the reduced graph.
Communities() [][]graph.Node

// Structure returns the community structure of
// the current level of the module clustering.
// Each slice in the returned value recursively
// describes the membership of a community at
// the current level by indexing via the node
// ID into the structure of the non-nil
// ReducedGraph returned by Expanded, or when the
// ReducedGraph is nil, by containing nodes
// from the original input graph.
//
// The returned value should not be mutated.
Structure() [][]graph.Node

// Expanded returns the next lower level of the
// module clustering or nil if at the lowest level.
//
// The returned ReducedGraph will be the same
// concrete type as the receiver.
Expanded() ReducedGraph
}

ReducedGraph is a modularised graph.

#### func Modularize ¶

func Modularize(g graph.Graph, resolution float64, src rand.Source) ReducedGraph

Modularize returns the hierarchical modularization of g at the given resolution using the Louvain algorithm. If src is nil, rand.Intn is used as the random generator. Modularize will panic if g has any edge with negative edge weight.

If g is undirected it is modularised to minimise

Q = 1/2m \sum_{ij} [ A_{ij} - (\gamma k_i k_j)/2m ] \delta(c_i,c_j),


If g is directed it is modularised to minimise

Q = 1/m \sum_{ij} [ A_{ij} - (\gamma k_i^in k_j^out)/m ] \delta(c_i,c_j).


The concrete type of the ReducedGraph will be a pointer to either a ReducedUndirected or a ReducedDirected depending on the type of g.

graph.Undirect may be used as a shim to allow modularization of directed graphs with the undirected modularity function.

#### type ReducedMultiplex ¶

type ReducedMultiplex interface {
Multiplex

// Communities returns the community memberships
// of the nodes in the graph used to generate
// the reduced graph.
Communities() [][]graph.Node

// Structure returns the community structure of
// the current level of the module clustering.
// Each slice in the returned value recursively
// describes the membership of a community at
// the current level by indexing via the node
// ID into the structure of the non-nil
// ReducedGraph returned by Expanded, or when the
// ReducedGraph is nil, by containing nodes
// from the original input graph.
//
// The returned value should not be mutated.
Structure() [][]graph.Node

// Expanded returns the next lower level of the
// module clustering or nil if at the lowest level.
//
// The returned ReducedGraph will be the same
// concrete type as the receiver.
Expanded() ReducedMultiplex
}

ReducedMultiplex is a modularised multiplex graph.

#### func ModularizeMultiplex ¶

func ModularizeMultiplex(g Multiplex, weights, resolutions []float64, all bool, src rand.Source) ReducedMultiplex

ModularizeMultiplex returns the hierarchical modularization of g at the given resolution using the Louvain algorithm. If all is true and g have negatively weighted layers, all communities will be searched during the modularization. If src is nil, rand.Intn is used as the random generator. ModularizeMultiplex will panic if g has any edge with edge weight that does not sign-match the layer weight.

If g is undirected it is modularised to minimise

Q = \sum w_{layer} \sum_{ij} [ A_{layer}*_{ij} - (\gamma_{layer} k_i k_j)/2m ] \delta(c_i,c_j).


If g is directed it is modularised to minimise

Q = \sum w_{layer} \sum_{ij} [ A_{layer}*_{ij} - (\gamma_{layer} k_i^in k_j^out)/m_{layer} ] \delta(c_i,c_j).


The concrete type of the ReducedMultiplex will be a pointer to a ReducedUndirectedMultiplex.

graph.Undirect may be used as a shim to allow modularization of directed graphs with the undirected modularity function.

#### type ReducedUndirected ¶

type ReducedUndirected struct {
// contains filtered or unexported fields
}

ReducedUndirected is an undirected graph of communities derived from a parent graph by reduction.

#### func (*ReducedUndirected) Communities ¶

func (g *ReducedUndirected) Communities() [][]graph.Node

Communities returns the community memberships of the nodes in the graph used to generate the reduced graph.

#### func (*ReducedUndirected) Edge ¶

func (g *ReducedUndirected) Edge(uid, vid int64) graph.Edge

Edge returns the edge from u to v if such an edge exists and nil otherwise. The node v must be directly reachable from u as defined by the From method.

#### func (*ReducedUndirected) EdgeBetween ¶

func (g *ReducedUndirected) EdgeBetween(xid, yid int64) graph.Edge

EdgeBetween returns the edge between nodes x and y.

#### func (*ReducedUndirected) Expanded ¶

func (g *ReducedUndirected) Expanded() ReducedGraph

Expanded returns the next lower level of the module clustering or nil if at the lowest level.

#### func (*ReducedUndirected) From ¶

func (g *ReducedUndirected) From(uid int64) graph.Nodes

From returns all nodes in g that can be reached directly from u.

#### func (*ReducedUndirected) HasEdgeBetween ¶

func (g *ReducedUndirected) HasEdgeBetween(xid, yid int64) bool

HasEdgeBetween returns whether an edge exists between nodes x and y.

#### func (*ReducedUndirected) Node ¶

func (g *ReducedUndirected) Node(id int64) graph.Node

Node returns the node with the given ID if it exists in the graph, and nil otherwise.

#### func (*ReducedUndirected) Nodes ¶

func (g *ReducedUndirected) Nodes() graph.Nodes

Nodes returns all the nodes in the graph.

#### func (*ReducedUndirected) Structure ¶

func (g *ReducedUndirected) Structure() [][]graph.Node

Structure returns the community structure of the current level of the module clustering. The first index of the returned value corresponds to the index of the nodes in the next higher level if it exists. The returned value should not be mutated.

#### func (*ReducedUndirected) Weight ¶

func (g *ReducedUndirected) Weight(xid, yid int64) (w float64, ok bool)

Weight returns the weight for the edge between x and y if Edge(x, y) returns a non-nil Edge. If x and y are the same node the internal node weight is returned. If there is no joining edge between the two nodes the weight value returned is zero. Weight returns true if an edge exists between x and y or if x and y have the same ID, false otherwise.

#### func (*ReducedUndirected) WeightedEdge ¶

func (g *ReducedUndirected) WeightedEdge(uid, vid int64) graph.WeightedEdge

WeightedEdge returns the weighted edge from u to v if such an edge exists and nil otherwise. The node v must be directly reachable from u as defined by the From method.

#### func (*ReducedUndirected) WeightedEdgeBetween ¶

func (g *ReducedUndirected) WeightedEdgeBetween(xid, yid int64) graph.WeightedEdge

WeightedEdgeBetween returns the weighted edge between nodes x and y.

#### type ReducedUndirectedMultiplex ¶

type ReducedUndirectedMultiplex struct {
// contains filtered or unexported fields
}

ReducedUndirectedMultiplex is an undirected graph of communities derived from a parent graph by reduction.

#### func (*ReducedUndirectedMultiplex) Communities ¶

func (g *ReducedUndirectedMultiplex) Communities() [][]graph.Node

Communities returns the community memberships of the nodes in the graph used to generate the reduced graph.

#### func (*ReducedUndirectedMultiplex) Depth ¶

func (g *ReducedUndirectedMultiplex) Depth() int

Depth returns the number of layers in the multiplex graph.

#### func (*ReducedUndirectedMultiplex) Expanded ¶

func (g *ReducedUndirectedMultiplex) Expanded() ReducedMultiplex

Expanded returns the next lower level of the module clustering or nil if at the lowest level.

#### func (*ReducedUndirectedMultiplex) Layer ¶

func (g *ReducedUndirectedMultiplex) Layer(l int) graph.Undirected

Layer returns the lth layer of the multiplex graph.

#### func (*ReducedUndirectedMultiplex) Nodes ¶

func (g *ReducedUndirectedMultiplex) Nodes() graph.Nodes

Nodes returns all the nodes in the graph.

#### func (*ReducedUndirectedMultiplex) Structure ¶

func (g *ReducedUndirectedMultiplex) Structure() [][]graph.Node

Structure returns the community structure of the current level of the module clustering. The first index of the returned value corresponds to the index of the nodes in the next higher level if it exists. The returned value should not be mutated.

#### type UndirectedLayers ¶

type UndirectedLayers []graph.Undirected

UndirectedLayers implements UndirectedMultiplex.

#### func NewUndirectedLayers ¶

func NewUndirectedLayers(layers ...graph.Undirected) (UndirectedLayers, error)

NewUndirectedLayers returns an UndirectedLayers using the provided layers ensuring there is a match between IDs for each layer.

#### func (UndirectedLayers) Depth ¶

func (g UndirectedLayers) Depth() int

Depth returns the depth of the multiplex graph.

#### func (UndirectedLayers) Layer ¶

func (g UndirectedLayers) Layer(l int) graph.Undirected

Layer returns the lth layer of the multiplex graph.

#### func (UndirectedLayers) Nodes ¶

func (g UndirectedLayers) Nodes() graph.Nodes

Nodes returns the nodes of the receiver.

#### type UndirectedMultiplex ¶

type UndirectedMultiplex interface {
Multiplex

// Layer returns the lth layer of the
// multiplex graph.
Layer(l int) graph.Undirected
}

UndirectedMultiplex is an undirected multiplex graph.