issue43658.go

     1  // Copyright ©2016 The Gonum Authors. All rights reserved.
     2  // Copyright 2021 The Go Authors. All rights reserved.
     3  // (above line required for our license-header checker)
     4  // Use of this source code is governed by a BSD-style
     5  // license that can be found in the LICENSE file.
     6  
     7  package community_test
     8  
     9  import (
    10  	"fmt"
    11  	"log"
    12  	"sort"
    13  
    14  	"golang.org/x/exp/rand"
    15  
    16  	"gonum.org/v1/gonum/graph/community"
    17  	"gonum.org/v1/gonum/graph/internal/ordered"
    18  	"gonum.org/v1/gonum/graph/simple"
    19  )
    20  
    21  func ExampleProfile_simple() {
    22  	// Profile calls Modularize which implements the Louvain modularization algorithm.
    23  	// Since this is a randomized algorithm we use a defined random source to ensure
    24  	// consistency between test runs. In practice, results will not differ greatly
    25  	// between runs with different PRNG seeds.
    26  	src := rand.NewSource(1)
    27  
    28  	// Create dumbell graph:
    29  	//
    30  	//  0       4
    31  	//  |\     /|
    32  	//  | 2 - 3 |
    33  	//  |/     \|
    34  	//  1       5
    35  	//
    36  	g := simple.NewUndirectedGraph()
    37  	for u, e := range smallDumbell {
    38  		for v := range e {
    39  			g.SetEdge(simple.Edge{F: simple.Node(u), T: simple.Node(v)})
    40  		}
    41  	}
    42  
    43  	// Get the profile of internal node weight for resolutions
    44  	// between 0.1 and 10 using logarithmic bisection.
    45  	p, err := community.Profile(
    46  		community.ModularScore(g, community.Weight, 10, src),
    47  		true, 1e-3, 0.1, 10,
    48  	)
    49  	if err != nil {
    50  		log.Fatal(err)
    51  	}
    52  
    53  	// Print out each step with communities ordered.
    54  	for _, d := range p {
    55  		comm := d.Communities()
    56  		for _, c := range comm {
    57  			sort.Sort(ordered.ByID(c))
    58  		}
    59  		sort.Sort(ordered.BySliceIDs(comm))
    60  		fmt.Printf("Low:%.2v High:%.2v Score:%v Communities:%v Q=%.3v\n",
    61  			d.Low, d.High, d.Score, comm, community.Q(g, comm, d.Low))
    62  	}
    63  
    64  	// Output:
    65  	// Low:0.1 High:0.29 Score:14 Communities:[[0 1 2 3 4 5]] Q=0.9
    66  	// Low:0.29 High:2.3 Score:12 Communities:[[0 1 2] [3 4 5]] Q=0.714
    67  	// Low:2.3 High:3.5 Score:4 Communities:[[0 1] [2] [3] [4 5]] Q=-0.31
    68  	// Low:3.5 High:10 Score:0 Communities:[[0] [1] [2] [3] [4] [5]] Q=-0.607
    69  }
    70  
    71  // intset is an integer set.
    72  type intset map[int]struct{}
    73  
    74  func linksTo(i ...int) intset {
    75  	if len(i) == 0 {
    76  		return nil
    77  	}
    78  	s := make(intset)
    79  	for _, v := range i {
    80  		s[v] = struct{}{}
    81  	}
    82  	return s
    83  }
    84  
    85  var (
    86  	smallDumbell = []intset{
    87  		0: linksTo(1, 2),
    88  		1: linksTo(2),
    89  		2: linksTo(3),
    90  		3: linksTo(4, 5),
    91  		4: linksTo(5),
    92  		5: nil,
    93  	}
    94  
    95  	// http://www.slate.com/blogs/the_world_/2014/07/17/the_middle_east_friendship_chart.html
    96  	middleEast = struct{ friends, complicated, enemies []intset }{
    97  		// green cells
    98  		friends: []intset{
    99  			0:  nil,
   100  			1:  linksTo(5, 7, 9, 12),
   101  			2:  linksTo(11),
   102  			3:  linksTo(4, 5, 10),
   103  			4:  linksTo(3, 5, 10),
   104  			5:  linksTo(1, 3, 4, 8, 10, 12),
   105  			6:  nil,
   106  			7:  linksTo(1, 12),
   107  			8:  linksTo(5, 9, 11),
   108  			9:  linksTo(1, 8, 12),
   109  			10: linksTo(3, 4, 5),
   110  			11: linksTo(2, 8),
   111  			12: linksTo(1, 5, 7, 9),
   112  		},
   113  
   114  		// yellow cells
   115  		complicated: []intset{
   116  			0:  linksTo(2, 4),
   117  			1:  linksTo(4, 8),
   118  			2:  linksTo(0, 3, 4, 5, 8, 9),
   119  			3:  linksTo(2, 8, 11),
   120  			4:  linksTo(0, 1, 2, 8),
   121  			5:  linksTo(2),
   122  			6:  nil,
   123  			7:  linksTo(9, 11),
   124  			8:  linksTo(1, 2, 3, 4, 10, 12),
   125  			9:  linksTo(2, 7, 11),
   126  			10: linksTo(8),
   127  			11: linksTo(3, 7, 9, 12),
   128  			12: linksTo(8, 11),
   129  		},
   130  
   131  		// red cells
   132  		enemies: []intset{
   133  			0:  linksTo(1, 3, 5, 6, 7, 8, 9, 10, 11, 12),
   134  			1:  linksTo(0, 2, 3, 6, 10, 11),
   135  			2:  linksTo(1, 6, 7, 10, 12),
   136  			3:  linksTo(0, 1, 6, 7, 9, 12),
   137  			4:  linksTo(6, 7, 9, 11, 12),
   138  			5:  linksTo(0, 6, 7, 9, 11),
   139  			6:  linksTo(0, 1, 2, 3, 4, 5, 7, 8, 9, 10, 11, 12),
   140  			7:  linksTo(0, 2, 3, 4, 5, 6, 8, 10),
   141  			8:  linksTo(0, 6, 7),
   142  			9:  linksTo(0, 3, 4, 5, 6, 10),
   143  			10: linksTo(0, 1, 2, 6, 7, 9, 11, 12),
   144  			11: linksTo(0, 1, 4, 5, 6, 10),
   145  			12: linksTo(0, 2, 3, 4, 6, 10),
   146  		},
   147  	}
   148  )
   149  
   150  var friends, enemies *simple.WeightedUndirectedGraph
   151  
   152  func init() {
   153  	friends = simple.NewWeightedUndirectedGraph(0, 0)
   154  	for u, e := range middleEast.friends {
   155  		// Ensure unconnected nodes are included.
   156  		if friends.Node(int64(u)) == nil {
   157  			friends.AddNode(simple.Node(u))
   158  		}
   159  		for v := range e {
   160  			friends.SetWeightedEdge(simple.WeightedEdge{F: simple.Node(u), T: simple.Node(v), W: 1})
   161  		}
   162  	}
   163  	enemies = simple.NewWeightedUndirectedGraph(0, 0)
   164  	for u, e := range middleEast.enemies {
   165  		// Ensure unconnected nodes are included.
   166  		if enemies.Node(int64(u)) == nil {
   167  			enemies.AddNode(simple.Node(u))
   168  		}
   169  		for v := range e {
   170  			enemies.SetWeightedEdge(simple.WeightedEdge{F: simple.Node(u), T: simple.Node(v), W: -1})
   171  		}
   172  	}
   173  }
   174  
   175  func ExampleProfile_multiplex() {
   176  	// Profile calls ModularizeMultiplex which implements the Louvain modularization
   177  	// algorithm. Since this is a randomized algorithm we use a defined random source
   178  	// to ensure consistency between test runs. In practice, results will not differ
   179  	// greatly between runs with different PRNG seeds.
   180  	src := rand.NewSource(1)
   181  
   182  	// The undirected graphs, friends and enemies, are the political relationships
   183  	// in the Middle East as described in the Slate article:
   184  	// http://www.slate.com/blogs/the_world_/2014/07/17/the_middle_east_friendship_chart.html
   185  	g, err := community.NewUndirectedLayers(friends, enemies)
   186  	if err != nil {
   187  		log.Fatal(err)
   188  	}
   189  	weights := []float64{1, -1}
   190  
   191  	// Get the profile of internal node weight for resolutions
   192  	// between 0.1 and 10 using logarithmic bisection.
   193  	p, err := community.Profile(
   194  		community.ModularMultiplexScore(g, weights, true, community.WeightMultiplex, 10, src),
   195  		true, 1e-3, 0.1, 10,
   196  	)
   197  	if err != nil {
   198  		log.Fatal(err)
   199  	}
   200  
   201  	// Print out each step with communities ordered.
   202  	for _, d := range p {
   203  		comm := d.Communities()
   204  		for _, c := range comm {
   205  			sort.Sort(ordered.ByID(c))
   206  		}
   207  		sort.Sort(ordered.BySliceIDs(comm))
   208  		fmt.Printf("Low:%.2v High:%.2v Score:%v Communities:%v Q=%.3v\n",
   209  			d.Low, d.High, d.Score, comm, community.QMultiplex(g, comm, weights, []float64{d.Low}))
   210  	}
   211  
   212  	// Output:
   213  	// 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]
   214  	// 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]
   215  	// 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]
   216  	// 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]
   217  	// 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]
   218  	// 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]
   219  	// 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]
   220  	// 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]
   221  	// 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]
   222  	// Low:4.3 High:10 Score:-54 Communities:[[0 1 2 3 4 6 7 8 9 10 11 12] [5]] Q=[-82 254]
   223  }
   224
View as plain text