All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Groups Pages
ModularityScoring.h
Go to the documentation of this file.
1 /*
2  * ModularityScoring.h
3  *
4  * Created on: 15.10.2012
5  * Author: Christian Staudt (christian.staudt@kit.edu)
6  */
7 
8 #ifndef MODULARITY_SCORING_H_
9 #define MODULARITY_SCORING_H_
10 
11 #include "EdgeScoring.h"
12 
13 #include "../structures/Partition.h"
14 
15 
16 namespace NetworKit {
17 
18 // TODO: implement modularity as in Python prototype
19 
23 template<typename T>
25 
26 protected:
27 
28  double totalEdgeWeight;
29 
30 public:
31 
37  ModularityScoring(Graph& G, double gTotalEdgeWeight = 0.0);
38 
40  virtual ~ModularityScoring() = default;
41 
42 
43  virtual void scoreEdges(int attrId);
44 
45 
57  virtual T edgeScore(node u, node v) const;
58 
59 
60 
61 // /**
62 // * Calculates the difference in modularity that would result from a merger of
63 // * two clusters.
64 // *
65 // */
66 // virtual double deltaMod(index c, index d) =0;
67 //
68 // virtual double cutweight(index c, index d) =0;
69 //
70 // virtual double weight(index c) =0;
71 };
72 
73 
74 template<typename T>
75 ModularityScoring<T>::ModularityScoring(Graph& G, double gTotalEdgeWeight) : EdgeScoring<T>(G),
76  totalEdgeWeight(gTotalEdgeWeight)
77 {
78  if (gTotalEdgeWeight == 0.0) {
79  this->totalEdgeWeight = this->G->totalEdgeWeight();
80  }
81 }
82 
83 template<typename T>
85  assert(totalEdgeWeight != 0.0);
86  double volume = 2.0 * totalEdgeWeight;
87  double nom1 = (this->G->weightedDegree(u) / volume);
88  double nom2 = (this->G->weightedDegree(v) / volume);
89  double deltaMod = (this->G->weight(u, v) / totalEdgeWeight) -
90  (nom1 * nom2);
91 // TRACE("volume: ", volume, ", deltaMod: ", deltaMod, ", totalew: ", totalEdgeWeight);
92  return deltaMod;
93 }
94 
95 template<typename T>
97 
98  // TODO: rewrite with new edge attribute system
99 
100  // this->G->forEdgesWithAttribute_double(attrId, [&](node u, node v, double attr) {
101  // attr = this->edgeScore(u, v);
102  // this->G->setAttribute_double(u, v, attrId, attr);
103  // });
104 }
105 
106 
107 } /* namespace NetworKit */
108 
109 #endif /* MODULARITY_H_ */
edgeweight totalEdgeWeight() const
Returns the sum of all edge weights.
Definition: Graph.cpp:866
Abstract base class for algorithms associating a score with an edge.
Definition: EdgeScoring.h:21
virtual ~ModularityScoring()=default
Default destructor.
virtual void scoreEdges(int attrId)
Definition: ModularityScoring.h:96
Definition: ModularityScoring.h:24
Graph * G
pointer to the graph
Definition: EdgeScoring.h:25
index node
Definition: Globals.h:23
A graph (with optional weights) and parallel iterator methods.
Definition: Graph.h:79
ModularityScoring(Graph &G, double gTotalEdgeWeight=0.0)
Definition: ModularityScoring.h:75
virtual T edgeScore(node u, node v) const
Returns an edge score for an edge (u,v) which expresses the modularity increase which can be gained b...
Definition: ModularityScoring.h:84
double totalEdgeWeight
total weight of the graph
Definition: ModularityScoring.h:28