sslouvain/src/SurpriseVertexPartition.cpp at master · BradhamLab/sslouvain · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
#include "SurpriseVertexPartition.h"

// ss modififications
SurpriseVertexPartition::SurpriseVertexPartition(Graph* graph,
  vector<size_t> const& membership,
  vector<bool> const& mutables) : MutableVertexPartition(graph,
                                                         membership,
                                                         mutables)
{ }

SurpriseVertexPartition::SurpriseVertexPartition(Graph* graph,
      vector<size_t> const& membership) :
        MutableVertexPartition(graph,
        membership)
{ }

SurpriseVertexPartition::SurpriseVertexPartition(Graph* graph) :
        MutableVertexPartition(graph)
{ }

SurpriseVertexPartition* SurpriseVertexPartition::create(Graph* graph)
{
  return new SurpriseVertexPartition(graph);
}

 SurpriseVertexPartition*  SurpriseVertexPartition::create(Graph* graph, vector<size_t> const& membership)
{
  return new  SurpriseVertexPartition(graph, membership);
}

SurpriseVertexPartition::~SurpriseVertexPartition()
{ }

double SurpriseVertexPartition::diff_move(size_t v, size_t new_comm)
{
  #ifdef DEBUG
    cerr << "virtual double SurpriseVertexPartition::diff_move(" << v << ", " << new_comm << ")" << endl;
  #endif
  size_t old_comm = this->membership(v);
  size_t nsize = this->graph->node_size(v);
  #ifdef DEBUG
    cerr << "\t" << "nsize: " << nsize << endl;
  #endif
  double diff = 0.0;
  double m = this->graph->total_weight();

  if (m == 0)
    return 0.0;

  if (new_comm != old_comm)
  {
    double normalise = (2.0 - this->graph->is_directed());
    size_t n = this->graph->total_size();
    size_t n2 = this->graph->possible_edges(n);

    #ifdef DEBUG
      cerr << "\t" << "Community: " << old_comm << " => " << new_comm << "." << endl;
      cerr << "\t" << "m: " << m << ", n2: " << n2 << "." << endl;
    #endif

    // Before move
    double mc = this->total_weight_in_all_comms();
    size_t nc2 = this->total_possible_edges_in_all_comms();
    #ifdef DEBUG
      cerr << "\t" << "mc: " << mc << ", nc2: " << nc2 << "." << endl;
    #endif

    // To old comm
    size_t n_old = this->csize(old_comm);
    double sw = this->graph->node_self_weight(v);
    double wtc = this->weight_to_comm(v, old_comm) - sw;
    double wfc = this->weight_from_comm(v, old_comm) - sw;
    #ifdef DEBUG
      cerr << "\t"  << "wtc: " << wtc << ", wfc: " << wfc << ", sw: " << sw << "." << endl;
    #endif
    double m_old = wtc/normalise + wfc/normalise + sw;
    #ifdef DEBUG
      cerr << "\t" << "m_old: " << m_old << ", n_old: " << n_old << "." << endl;
    #endif

    // To new comm
    size_t n_new = this->csize(new_comm);
    wtc = this->weight_to_comm(v, new_comm);
    wfc = this->weight_from_comm(v, new_comm);
    sw = this->graph->node_self_weight(v);
    #ifdef DEBUG
      cerr << "\t"  << "wtc: " << wtc << ", wfc: " << wfc << ", sw: " << sw << "." << endl;
    #endif
    double m_new = wtc/normalise + wfc/normalise + sw;
    #ifdef DEBUG
      cerr << "\t" << "m_new: " << m_new << ", n_new: " << n_new << "." << endl;
    #endif

    double q = mc/m;
    double s = (double)nc2/(double)n2;
    double q_new = (mc - m_old + m_new)/m;
    #ifdef DEBUG
      cerr << "\t" << "mc - m_old + m_new=" << (mc - m_old + m_new) << endl;
    #endif
    double delta_nc2 = 2.0*nsize*(ptrdiff_t)(n_new - n_old + nsize)/normalise;
    double s_new = (double)(nc2 + delta_nc2)/(double)n2;
    #ifdef DEBUG
      cerr << "\t" << "delta_nc2=" << delta_nc2 << endl;
    #endif
    #ifdef DEBUG
      cerr << "\t" << "q:\t" << q << ", s:\t"  << s << "." << endl;
      cerr << "\t" << "q_new:\t" << q_new << ", s_new:\t"  << s_new << "." << endl;
    #endif
    diff = m*(KLL(q_new, s_new) - KLL(q, s));

    #ifdef DEBUG
      cerr << "\t" << "diff: " << diff << "." << endl;
    #endif
  }
  #ifdef DEBUG
    cerr << "exit double SurpriseVertexPartition::diff_move(" << v << ", " << new_comm << ")" << endl;
    cerr << "return " << diff << endl << endl;
  #endif
  return diff;
}

double SurpriseVertexPartition::quality()
{
  #ifdef DEBUG
    cerr << "double SurpriseVertexPartition::quality()" << endl;
  #endif

  double mc = this->total_weight_in_all_comms();
  size_t nc2 = this->total_possible_edges_in_all_comms();
  double m = this->graph->total_weight();
  size_t n = this->graph->total_size();

  if (m == 0)
    return 0.0;

  size_t n2 = this->graph->possible_edges(n);

  #ifdef DEBUG
    cerr << "\t" << "mc=" << mc << ", m=" << m << ", nc2=" << nc2 << ", n2=" << n2 << "." << endl;
  #endif
  double q = mc/m;
  double s = (double)nc2/(double)n2;
  #ifdef DEBUG
    cerr << "\t" << "q:\t" << q << ", s:\t"  << s << "." << endl;
  #endif
  double S = m*KLL(q,s);
  #ifdef DEBUG
    cerr << "exit SurpriseVertexPartition::quality()" << endl;
    cerr << "return " << S << endl << endl;
  #endif
  return S;
}