community

package
v0.6.5 Latest Latest
Warning

This package is not in the latest version of its module.

Go to latest
Published: Feb 5, 2020 License: BSD-3-Clause Imports: 12 Imported by: 0

Documentation

Overview

Package community provides graph community detection functions.

Index

Examples

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)
// Profile calls ModularizeMultiplex which implements the Louvain modularization
// algorithm. Since this is a randomized algorithm we use a defined random source
// to ensure consistency between test runs. In practice, results will not differ
// greatly between runs with different PRNG seeds.
src := rand.NewSource(1)

// The undirected graphs, friends and enemies, are the political relationships
// in the Middle East as described in the Slate article:
// http://www.slate.com/blogs/the_world_/2014/07/17/the_middle_east_friendship_chart.html
g, err := NewUndirectedLayers(friends, enemies)
if err != nil {
	log.Fatal(err)
}
weights := []float64{1, -1}

// Get the profile of internal node weight for resolutions
// between 0.1 and 10 using logarithmic bisection.
p, err := Profile(ModularMultiplexScore(g, weights, true, WeightMultiplex, 10, src), true, 1e-3, 0.1, 10)
if err != nil {
	log.Fatal(err)
}

// Print out each step with communities ordered.
for _, d := range p {
	comm := d.Communities()
	for _, c := range comm {
		sort.Sort(ordered.ByID(c))
	}
	sort.Sort(ordered.BySliceIDs(comm))
	fmt.Printf("Low:%.2v High:%.2v Score:%v Communities:%v Q=%.3v\n",
		d.Low, d.High, d.Score, comm, QMultiplex(g, comm, weights, []float64{d.Low}))
}
Output:

Low:0.1 High:0.72 Score:26 Communities:[[0] [1 7 9 12] [2 8 11] [3 4 5 10] [6]] 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] [5]] Q=[-82 254]
Example (Simple)
// Profile calls Modularize which implements the Louvain modularization algorithm.
// Since this is a randomized algorithm we use a defined random source to ensure
// consistency between test runs. In practice, results will not differ greatly
// between runs with different PRNG seeds.
src := rand.NewSource(1)

// Create dumbell graph:
//
//  0       4
//  |\     /|
//  | 2 - 3 |
//  |/     \|
//  1       5
//
g := simple.NewUndirectedGraph()
for u, e := range smallDumbell {
	for v := range e {
		g.SetEdge(simple.Edge{F: simple.Node(u), T: simple.Node(v)})
	}
}

// Get the profile of internal node weight for resolutions
// between 0.1 and 10 using logarithmic bisection.
p, err := Profile(ModularScore(g, Weight, 10, src), true, 1e-3, 0.1, 10)
if err != nil {
	log.Fatal(err)
}

// Print out each step with communities ordered.
for _, d := range p {
	comm := d.Communities()
	for _, c := range comm {
		sort.Sort(ordered.ByID(c))
	}
	sort.Sort(ordered.BySliceIDs(comm))
	fmt.Printf("Low:%.2v High:%.2v Score:%v Communities:%v Q=%.3v\n",
		d.Low, d.High, d.Score, comm, Q(g, comm, d.Low))
}
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] [2] [3] [4 5]] Q=-0.31
Low:3.5 High:10 Score:0 Communities:[[0] [1] [2] [3] [4] [5]] 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

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

func (*ReducedDirectedMultiplex) Layer

Layer returns the lth layer of the multiplex graph.

func (*ReducedDirectedMultiplex) 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

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

func (*ReducedUndirectedMultiplex) Layer

Layer returns the lth layer of the multiplex graph.

func (*ReducedUndirectedMultiplex) 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.

Jump to

Keyboard shortcuts

? : This menu
/ : Search site
f or F : Jump to
y or Y : Canonical URL