louvain_undirected_multiplex.go

// Copyright ©2015 The Gonum Authors. All rights reserved.
// Use of this source code is governed by a BSD-style
// license that can be found in the LICENSE file.

package community

import (
	"fmt"
	"math"
	"sort"

	"golang.org/x/exp/rand"

	"gonum.org/v1/gonum/graph"
	"gonum.org/v1/gonum/graph/internal/ordered"
	"gonum.org/v1/gonum/graph/internal/set"
	"gonum.org/v1/gonum/graph/iterator"
)

// UndirectedMultiplex is an undirected multiplex graph.
type UndirectedMultiplex interface {
	Multiplex

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

// qUndirectedMultiplex 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.
// qUndirectedMultiplex will panic if the graph has any layer weight-scaled edge with
// negative edge weight.
//
//  Q_{layer} = w_{layer} \sum_{ij} [ A_{layer}*_{ij} - (\gamma_{layer} k_i k_j)/2m ] \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 qUndirectedMultiplex(g UndirectedMultiplex, communities [][]graph.Node, weights, resolutions []float64) []float64 {
	q := make([]float64, g.Depth())
	nodes := graph.NodesOf(g.Nodes())
	layerWeight := 1.0
	layerResolution := 1.0
	if len(resolutions) == 1 {
		layerResolution = resolutions[0]
	}
	for l := 0; l < g.Depth(); l++ {
		layer := g.Layer(l)

		if weights != nil {
			layerWeight = weights[l]
		}
		if layerWeight == 0 {
			continue
		}

		if len(resolutions) > 1 {
			layerResolution = resolutions[l]
		}

		var weight func(xid, yid int64) float64
		if layerWeight < 0 {
			weight = negativeWeightFuncFor(layer)
		} else {
			weight = positiveWeightFuncFor(layer)
		}

		// Calculate the total edge weight of the layer
		// and the table of penetrating edge weight sums.
		var m2 float64
		k := make(map[int64]float64, len(nodes))
		for _, u := range nodes {
			uid := u.ID()
			w := weight(uid, uid)
			to := layer.From(uid)
			for to.Next() {
				w += weight(uid, to.Node().ID())
			}
			m2 += w
			k[uid] = w
		}

		if communities == nil {
			var qLayer float64
			for _, u := range nodes {
				uid := u.ID()
				kU := k[uid]
				qLayer += weight(uid, uid) - layerResolution*kU*kU/m2
			}
			q[l] = layerWeight * qLayer
			continue
		}

		// Iterate over the communities, calculating
		// the non-self edge weights for the upper
		// triangle and adjust the diagonal.
		var qLayer float64
		for _, c := range communities {
			for i, u := range c {
				uid := u.ID()
				kU := k[uid]
				qLayer += weight(uid, uid) - layerResolution*kU*kU/m2
				for _, v := range c[i+1:] {
					vid := v.ID()
					qLayer += 2 * (weight(uid, vid) - layerResolution*kU*k[vid]/m2)
				}
			}
		}
		q[l] = layerWeight * qLayer
	}

	return q
}

// UndirectedLayers implements UndirectedMultiplex.
type UndirectedLayers []graph.Undirected

// NewUndirectedLayers returns an UndirectedLayers using the provided layers
// ensuring there is a match between IDs for each layer.
func NewUndirectedLayers(layers ...graph.Undirected) (UndirectedLayers, error) {
	if len(layers) == 0 {
		return nil, nil
	}
	base := make(set.Int64s)
	nodes := layers[0].Nodes()
	for nodes.Next() {
		base.Add(nodes.Node().ID())
	}
	for i, l := range layers[1:] {
		next := make(set.Int64s)
		nodes := l.Nodes()
		for nodes.Next() {
			next.Add(nodes.Node().ID())
		}
		if !set.Int64sEqual(next, base) {
			return nil, fmt.Errorf("community: layer ID mismatch between layers: %d", i+1)
		}
	}
	return layers, nil
}

// Nodes returns the nodes of the receiver.
func (g UndirectedLayers) Nodes() graph.Nodes {
	if len(g) == 0 {
		return nil
	}
	return g[0].Nodes()
}

// Depth returns the depth of the multiplex graph.
func (g UndirectedLayers) Depth() int { return len(g) }

// Layer returns the lth layer of the multiplex graph.
func (g UndirectedLayers) Layer(l int) graph.Undirected { return g[l] }

// louvainUndirectedMultiplex returns the hierarchical modularization of g at the given resolution
// using the Louvain algorithm. If all is true and g has negatively weighted layers, all
// communities will be searched during the modularization. If src is nil, rand.Intn is
// used as the random generator. louvainUndirectedMultiplex will panic if g has any edge with
// edge weight that does not sign-match the layer weight.
//
// graph.Undirect may be used as a shim to allow modularization of directed graphs.
func louvainUndirectedMultiplex(g UndirectedMultiplex, weights, resolutions []float64, all bool, src rand.Source) *ReducedUndirectedMultiplex {
	if weights != nil && len(weights) != g.Depth() {
		panic("community: weights vector length mismatch")
	}
	if resolutions != nil && len(resolutions) != 1 && len(resolutions) != g.Depth() {
		panic("community: resolutions vector length mismatch")
	}

	// See louvain.tex for a detailed description
	// of the algorithm used here.

	c := reduceUndirectedMultiplex(g, nil, weights)
	rnd := rand.Intn
	if src != nil {
		rnd = rand.New(src).Intn
	}
	for {
		l := newUndirectedMultiplexLocalMover(c, c.communities, weights, resolutions, all)
		if l == nil {
			return c
		}
		if done := l.localMovingHeuristic(rnd); done {
			return c
		}
		c = reduceUndirectedMultiplex(c, l.communities, weights)
	}
}

// ReducedUndirectedMultiplex is an undirected graph of communities derived from a
// parent graph by reduction.
type ReducedUndirectedMultiplex struct {
	// nodes is the set of nodes held
	// by the graph. In a ReducedUndirectedMultiplex
	// the node ID is the index into
	// nodes.
	nodes  []multiplexCommunity
	layers []undirectedEdges

	// communities is the community
	// structure of the graph.
	communities [][]graph.Node

	parent *ReducedUndirectedMultiplex
}

var (
	_ UndirectedMultiplex      = (*ReducedUndirectedMultiplex)(nil)
	_ graph.WeightedUndirected = (*undirectedLayerHandle)(nil)
)

// Nodes returns all the nodes in the graph.
func (g *ReducedUndirectedMultiplex) Nodes() graph.Nodes {
	nodes := make([]graph.Node, len(g.nodes))
	for i := range g.nodes {
		nodes[i] = node(i)
	}
	return iterator.NewOrderedNodes(nodes)
}

// Depth returns the number of layers in the multiplex graph.
func (g *ReducedUndirectedMultiplex) Depth() int { return len(g.layers) }

// Layer returns the lth layer of the multiplex graph.
func (g *ReducedUndirectedMultiplex) Layer(l int) graph.Undirected {
	return undirectedLayerHandle{multiplex: g, layer: l}
}

// Communities returns the community memberships of the nodes in the
// graph used to generate the reduced graph.
func (g *ReducedUndirectedMultiplex) Communities() [][]graph.Node {
	communities := make([][]graph.Node, len(g.communities))
	if g.parent == nil {
		for i, members := range g.communities {
			comm := make([]graph.Node, len(members))
			for j, n := range members {
				nodes := g.nodes[n.ID()].nodes
				if len(nodes) != 1 {
					panic("community: unexpected number of nodes in base graph community")
				}
				comm[j] = nodes[0]
			}
			communities[i] = comm
		}
		return communities
	}
	sub := g.parent.Communities()
	for i, members := range g.communities {
		var comm []graph.Node
		for _, n := range members {
			comm = append(comm, sub[n.ID()]...)
		}
		communities[i] = comm
	}
	return communities
}

// 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 (g *ReducedUndirectedMultiplex) Structure() [][]graph.Node {
	return g.communities
}

// Expanded returns the next lower level of the module clustering or nil
// if at the lowest level.
func (g *ReducedUndirectedMultiplex) Expanded() ReducedMultiplex {
	return g.parent
}

// reduceUndirectedMultiplex returns a reduced graph constructed from g divided
// into the given communities. The communities value is mutated
// by the call to reduceUndirectedMultiplex. If communities is nil and g is a
// ReducedUndirectedMultiplex, it is returned unaltered.
func reduceUndirectedMultiplex(g UndirectedMultiplex, communities [][]graph.Node, weights []float64) *ReducedUndirectedMultiplex {
	if communities == nil {
		if r, ok := g.(*ReducedUndirectedMultiplex); ok {
			return r
		}

		nodes := graph.NodesOf(g.Nodes())
		// TODO(kortschak) This sort is necessary really only
		// for testing. In practice we would not be using the
		// community provided by the user for a Q calculation.
		// Probably we should use a function to map the
		// communities in the test sets to the remapped order.
		sort.Sort(ordered.ByID(nodes))
		communities = make([][]graph.Node, len(nodes))
		for i := range nodes {
			communities[i] = []graph.Node{node(i)}
		}

		r := ReducedUndirectedMultiplex{
			nodes:       make([]multiplexCommunity, len(nodes)),
			layers:      make([]undirectedEdges, g.Depth()),
			communities: communities,
		}
		communityOf := make(map[int64]int, len(nodes))
		for i, n := range nodes {
			r.nodes[i] = multiplexCommunity{id: i, nodes: []graph.Node{n}, weights: make([]float64, depth(weights))}
			communityOf[n.ID()] = i
		}
		for i := range r.layers {
			r.layers[i] = undirectedEdges{
				edges:   make([][]int, len(nodes)),
				weights: make(map[[2]int]float64),
			}
		}
		w := 1.0
		for l := 0; l < g.Depth(); l++ {
			layer := g.Layer(l)
			if weights != nil {
				w = weights[l]
			}
			if w == 0 {
				continue
			}
			var sign float64
			var weight func(xid, yid int64) float64
			if w < 0 {
				sign, weight = -1, negativeWeightFuncFor(layer)
			} else {
				sign, weight = 1, positiveWeightFuncFor(layer)
			}
			for _, u := range nodes {
				var out []int
				uid := u.ID()
				ucid := communityOf[uid]
				to := layer.From(uid)
				for to.Next() {
					vid := to.Node().ID()
					vcid := communityOf[vid]
					if vcid != ucid {
						out = append(out, vcid)
					}
					if ucid < vcid {
						// Only store the weight once.
						r.layers[l].weights[[2]int{ucid, vcid}] = sign * weight(uid, vid)
					}
				}
				r.layers[l].edges[ucid] = out
			}
		}
		return &r
	}

	// Remove zero length communities destructively.
	var commNodes int
	for i := 0; i < len(communities); {
		comm := communities[i]
		if len(comm) == 0 {
			communities[i] = communities[len(communities)-1]
			communities[len(communities)-1] = nil
			communities = communities[:len(communities)-1]
		} else {
			commNodes += len(comm)
			i++
		}
	}

	r := ReducedUndirectedMultiplex{
		nodes:  make([]multiplexCommunity, len(communities)),
		layers: make([]undirectedEdges, g.Depth()),
	}
	communityOf := make(map[int64]int, commNodes)
	for i, comm := range communities {
		r.nodes[i] = multiplexCommunity{id: i, nodes: comm, weights: make([]float64, depth(weights))}
		for _, n := range comm {
			communityOf[n.ID()] = i
		}
	}
	for i := range r.layers {
		r.layers[i] = undirectedEdges{
			edges:   make([][]int, len(communities)),
			weights: make(map[[2]int]float64),
		}
	}
	r.communities = make([][]graph.Node, len(communities))
	for i := range r.communities {
		r.communities[i] = []graph.Node{node(i)}
	}
	if g, ok := g.(*ReducedUndirectedMultiplex); ok {
		// Make sure we retain the truncated
		// community structure.
		g.communities = communities
		r.parent = g
	}
	w := 1.0
	for l := 0; l < g.Depth(); l++ {
		layer := g.Layer(l)
		if weights != nil {
			w = weights[l]
		}
		if w == 0 {
			continue
		}
		var sign float64
		var weight func(xid, yid int64) float64
		if w < 0 {
			sign, weight = -1, negativeWeightFuncFor(layer)
		} else {
			sign, weight = 1, positiveWeightFuncFor(layer)
		}
		for ucid, comm := range communities {
			var out []int
			for i, u := range comm {
				uid := u.ID()
				r.nodes[ucid].weights[l] += sign * weight(uid, uid)
				for _, v := range comm[i+1:] {
					r.nodes[ucid].weights[l] += 2 * sign * weight(uid, v.ID())
				}
				to := layer.From(uid)
				for to.Next() {
					vid := to.Node().ID()
					vcid := communityOf[vid]
					found := false
					for _, e := range out {
						if e == vcid {
							found = true
							break
						}
					}
					if !found && vcid != ucid {
						out = append(out, vcid)
					}
					if ucid < vcid {
						// Only store the weight once.
						r.layers[l].weights[[2]int{ucid, vcid}] += sign * weight(uid, vid)
					}
				}
			}
			r.layers[l].edges[ucid] = out
		}
	}
	return &r
}

// undirectedLayerHandle is a handle to a multiplex graph layer.
type undirectedLayerHandle struct {
	// multiplex is the complete
	// multiplex graph.
	multiplex *ReducedUndirectedMultiplex

	// layer is an index into the
	// multiplex for the current
	// layer.
	layer int
}

// Node returns the node with the given ID if it exists in the graph,
// and nil otherwise.
func (g undirectedLayerHandle) Node(id int64) graph.Node {
	if g.has(id) {
		return g.multiplex.nodes[id]
	}
	return nil
}

// has returns whether the node exists within the graph.
func (g undirectedLayerHandle) has(id int64) bool {
	return 0 <= id && id < int64(len(g.multiplex.nodes))
}

// Nodes returns all the nodes in the graph.
func (g undirectedLayerHandle) Nodes() graph.Nodes {
	nodes := make([]graph.Node, len(g.multiplex.nodes))
	for i := range g.multiplex.nodes {
		nodes[i] = node(i)
	}
	return iterator.NewOrderedNodes(nodes)
}

// From returns all nodes in g that can be reached directly from u.
func (g undirectedLayerHandle) From(uid int64) graph.Nodes {
	out := g.multiplex.layers[g.layer].edges[uid]
	nodes := make([]graph.Node, len(out))
	for i, vid := range out {
		nodes[i] = g.multiplex.nodes[vid]
	}
	return iterator.NewOrderedNodes(nodes)
}

// HasEdgeBetween returns whether an edge exists between nodes x and y.
func (g undirectedLayerHandle) HasEdgeBetween(xid, yid int64) bool {
	if xid == yid || !isValidID(xid) || !isValidID(yid) {
		return false
	}
	if xid > yid {
		xid, yid = yid, xid
	}
	_, ok := g.multiplex.layers[g.layer].weights[[2]int{int(xid), int(yid)}]
	return ok
}

// 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 (g undirectedLayerHandle) Edge(uid, vid int64) graph.Edge {
	return g.WeightedEdgeBetween(uid, vid)
}

// 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 (g undirectedLayerHandle) WeightedEdge(uid, vid int64) graph.WeightedEdge {
	return g.WeightedEdgeBetween(uid, vid)
}

// EdgeBetween returns the edge between nodes x and y.
func (g undirectedLayerHandle) EdgeBetween(xid, yid int64) graph.Edge {
	return g.WeightedEdgeBetween(xid, yid)
}

// WeightedEdgeBetween returns the weighted edge between nodes x and y.
func (g undirectedLayerHandle) WeightedEdgeBetween(xid, yid int64) graph.WeightedEdge {
	if xid == yid || !isValidID(xid) || !isValidID(yid) {
		return nil
	}
	if yid < xid {
		xid, yid = yid, xid
	}
	w, ok := g.multiplex.layers[g.layer].weights[[2]int{int(xid), int(yid)}]
	if !ok {
		return nil
	}
	return multiplexEdge{from: g.multiplex.nodes[xid], to: g.multiplex.nodes[yid], weight: w}
}

// 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 (g undirectedLayerHandle) Weight(xid, yid int64) (w float64, ok bool) {
	if !isValidID(xid) || !isValidID(yid) {
		return 0, false
	}
	if xid == yid {
		return g.multiplex.nodes[xid].weights[g.layer], true
	}
	if xid > yid {
		xid, yid = yid, xid
	}
	w, ok = g.multiplex.layers[g.layer].weights[[2]int{int(xid), int(yid)}]
	return w, ok
}

// undirectedMultiplexLocalMover is a step in graph modularity optimization.
type undirectedMultiplexLocalMover struct {
	g *ReducedUndirectedMultiplex

	// nodes is the set of working nodes.
	nodes []graph.Node
	// edgeWeightOf is the weighted degree
	// of each node indexed by ID.
	edgeWeightOf [][]float64

	// m2 is the total sum of
	// edge weights in g.
	m2 []float64

	// weight is the weight function
	// provided by g or a function
	// that returns the Weight value
	// of the non-nil edge between x
	// and y.
	weight []func(xid, yid int64) float64

	// communities is the current
	// division of g.
	communities [][]graph.Node
	// memberships is a mapping between
	// node ID and community membership.
	memberships []int

	// resolution is the Reichardt and
	// Bornholdt γ parameter as defined
	// in doi:10.1103/PhysRevE.74.016110.
	resolutions []float64

	// weights is the layer weights for
	// the modularisation.
	weights []float64

	// searchAll specifies whether the local
	// mover should consider non-connected
	// communities during the local moving
	// heuristic.
	searchAll bool

	// moved indicates that a call to
	// move has been made since the last
	// call to shuffle.
	moved bool

	// changed indicates that a move
	// has been made since the creation
	// of the local mover.
	changed bool
}

// newUndirectedMultiplexLocalMover returns a new undirectedMultiplexLocalMover initialized with
// the graph g, a set of communities and a modularity resolution parameter. The
// node IDs of g must be contiguous in [0,n) where n is the number of nodes.
// If g has a zero edge weight sum, nil is returned.
func newUndirectedMultiplexLocalMover(g *ReducedUndirectedMultiplex, communities [][]graph.Node, weights, resolutions []float64, all bool) *undirectedMultiplexLocalMover {
	nodes := graph.NodesOf(g.Nodes())
	l := undirectedMultiplexLocalMover{
		g:            g,
		nodes:        nodes,
		edgeWeightOf: make([][]float64, g.Depth()),
		m2:           make([]float64, g.Depth()),
		communities:  communities,
		memberships:  make([]int, len(nodes)),
		resolutions:  resolutions,
		weights:      weights,
		weight:       make([]func(xid, yid int64) float64, g.Depth()),
	}

	// Calculate the total edge weight of the graph
	// and degree weights for each node.
	var zero int
	for i := 0; i < g.Depth(); i++ {
		l.edgeWeightOf[i] = make([]float64, len(nodes))
		var weight func(xid, yid int64) float64

		if weights != nil {
			if weights[i] == 0 {
				zero++
				continue
			}
			if weights[i] < 0 {
				weight = negativeWeightFuncFor(g.Layer(i))
				l.searchAll = all
			} else {
				weight = positiveWeightFuncFor(g.Layer(i))
			}
		} else {
			weight = positiveWeightFuncFor(g.Layer(i))
		}

		l.weight[i] = weight
		layer := g.Layer(i)
		for _, u := range l.nodes {
			uid := u.ID()
			w := weight(uid, uid)
			to := layer.From(uid)
			for to.Next() {
				w += weight(uid, to.Node().ID())
			}
			l.edgeWeightOf[i][uid] = w
			l.m2[i] += w
		}
		if l.m2[i] == 0 {
			zero++
		}
	}
	if zero == g.Depth() {
		return nil
	}

	// Assign membership mappings.
	for i, c := range communities {
		for _, u := range c {
			l.memberships[u.ID()] = i
		}
	}

	return &l
}

// localMovingHeuristic performs the Louvain local moving heuristic until
// no further moves can be made. It returns a boolean indicating that the
// undirectedMultiplexLocalMover has not made any improvement to the community
// structure and so the Louvain algorithm is done.
func (l *undirectedMultiplexLocalMover) localMovingHeuristic(rnd func(int) int) (done bool) {
	for {
		l.shuffle(rnd)
		for _, n := range l.nodes {
			dQ, dst, src := l.deltaQ(n)
			if dQ <= deltaQtol {
				continue
			}
			l.move(dst, src)
		}
		if !l.moved {
			return !l.changed
		}
	}
}

// shuffle performs a Fisher-Yates shuffle on the nodes held by the
// undirectedMultiplexLocalMover using the random source rnd which should return
// an integer in the range [0,n).
func (l *undirectedMultiplexLocalMover) shuffle(rnd func(n int) int) {
	l.moved = false
	for i := range l.nodes[:len(l.nodes)-1] {
		j := i + rnd(len(l.nodes)-i)
		l.nodes[i], l.nodes[j] = l.nodes[j], l.nodes[i]
	}
}

// move moves the node at src to the community at dst.
func (l *undirectedMultiplexLocalMover) move(dst int, src commIdx) {
	l.moved = true
	l.changed = true

	srcComm := l.communities[src.community]
	n := srcComm[src.node]

	l.memberships[n.ID()] = dst

	l.communities[dst] = append(l.communities[dst], n)
	srcComm[src.node], srcComm[len(srcComm)-1] = srcComm[len(srcComm)-1], nil
	l.communities[src.community] = srcComm[:len(srcComm)-1]
}

// deltaQ returns the highest gain in modularity attainable by moving
// n from its current community to another connected community and
// the index of the chosen destination. The index into the
// undirectedMultiplexLocalMover's communities field is returned in src if n
// is in communities.
func (l *undirectedMultiplexLocalMover) deltaQ(n graph.Node) (deltaQ float64, dst int, src commIdx) {
	id := n.ID()

	var iterator minTaker
	if l.searchAll {
		iterator = &dense{n: len(l.communities)}
	} else {
		// Find communities connected to n.
		connected := make(set.Ints)
		// The following for loop is equivalent to:
		//
		//  for i := 0; i < l.g.Depth(); i++ {
		//  	for _, v := range l.g.Layer(i).From(n) {
		//  		connected.Add(l.memberships[v.ID()])
		//  	}
		//  }
		//
		// This is done to avoid an allocation for
		// each layer.
		for _, layer := range l.g.layers {
			for _, vid := range layer.edges[id] {
				connected.Add(l.memberships[vid])
			}
		}
		// Insert the node's own community.
		connected.Add(l.memberships[id])
		iterator = newSlice(connected)
	}

	// Calculate the highest modularity gain
	// from moving into another community and
	// keep the index of that community.
	var dQremove float64
	dQadd, dst, src := math.Inf(-1), -1, commIdx{-1, -1}
	var i int
	for iterator.TakeMin(&i) {
		c := l.communities[i]
		var removal bool
		var _dQadd float64
		for layer := 0; layer < l.g.Depth(); layer++ {
			m2 := l.m2[layer]
			if m2 == 0 {
				// Do not consider layers with zero sum edge weight.
				continue
			}
			w := 1.0
			if l.weights != nil {
				w = l.weights[layer]
			}
			if w == 0 {
				// Do not consider layers with zero weighting.
				continue
			}

			var k_aC, sigma_totC float64 // C is a substitution for ^𝛼 or ^𝛽.
			removal = false
			for j, u := range c {
				uid := u.ID()
				if uid == id {
					// Only mark and check src community on the first layer.
					if layer == 0 {
						if src.community != -1 {
							panic("community: multiple sources")
						}
						src = commIdx{i, j}
					}
					removal = true
				}

				k_aC += l.weight[layer](id, uid)
				// sigma_totC could be kept for each community
				// and updated for moves, changing the calculation
				// of sigma_totC here from O(n_c) to O(1), but
				// in practice the time savings do not appear
				// to be compelling and do not make up for the
				// increase in code complexity and space required.
				sigma_totC += l.edgeWeightOf[layer][uid]
			}

			a_aa := l.weight[layer](id, id)
			k_a := l.edgeWeightOf[layer][id]
			gamma := 1.0
			if l.resolutions != nil {
				if len(l.resolutions) == 1 {
					gamma = l.resolutions[0]
				} else {
					gamma = l.resolutions[layer]
				}
			}

			// See louvain.tex for a derivation of these equations.
			// The weighting term, w, is described in V Traag,
			// "Algorithms and dynamical models for communities and
			// reputation in social networks", chapter 5.
			// http://www.traag.net/wp/wp-content/papercite-data/pdf/traag_algorithms_2013.pdf
			switch {
			case removal:
				// The community c was the current community,
				// so calculate the change due to removal.
				dQremove += w * (k_aC /*^𝛼*/ - a_aa - gamma*k_a*(sigma_totC /*^𝛼*/ -k_a)/m2)

			default:
				// Otherwise calculate the change due to an addition
				// to c.
				_dQadd += w * (k_aC /*^𝛽*/ - gamma*k_a*sigma_totC /*^𝛽*/ /m2)
			}
		}
		if !removal && _dQadd > dQadd {
			dQadd = _dQadd
			dst = i
		}
	}

	return 2 * (dQadd - dQremove), dst, src
}