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 

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.

Source Files

View all Source files

Jump to

Keyboard shortcuts

? : This menu
/ : Search site
f or F : Jump to
y or Y : Canonical URL
go.dev uses cookies from Google to deliver and enhance the quality of its services and to analyze traffic. Learn more.