All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Groups Pages
AlgebraicSpanningEdgeCentrality.h
Go to the documentation of this file.
1 /*
2  * AlgebraicSpanningEdgeCentrality.h
3  *
4  * Created on: Jul 12, 2016
5  * Author: Michael Wegner (michael.wegner@student.kit.edu)
6  */
7 
8 #ifndef NETWORKIT_CPP_ALGEBRAIC_ALGORITHMS_ALGEBRAICSPANNINGEDGECENTRALITY_H_
9 #define NETWORKIT_CPP_ALGEBRAIC_ALGORITHMS_ALGEBRAICSPANNINGEDGECENTRALITY_H_
10 
11 #include "../../centrality/Centrality.h"
12 #include "../../numerics/LAMG/Lamg.h"
13 
14 namespace NetworKit {
15 
20 template<class Matrix>
22 public:
30  AlgebraicSpanningEdgeCentrality(const Graph& graph, double tol = 0.1) : Centrality(graph), tol(tol) {}
31 
32 
36  void run() override;
37 
41  void runApproximation();
42 
43 private:
44  double tol;
45 };
46 
47 template<class Matrix>
49  const count n = G.numberOfNodes();
50  const count m = G.numberOfEdges();
51  scoreData.clear();
52  scoreData.resize(m, 0.0);
53 
54 
55  std::vector<Vector> rhs(m, Vector(n));
56  this->G.parallelForEdges([&](node u, node v, edgeid e) {
57  rhs[e][u] = +1;
58  rhs[e][v] = -1;
59  });
60 
61  std::vector<Vector> solutions(m, Vector(n));
62 
63  Lamg<Matrix> lamg(1e-5);
64  lamg.setupConnected(Matrix::laplacianMatrix(this->G));
65  lamg.parallelSolve(rhs, solutions);
66 
67  this->G.parallelForEdges([&](node u, node v, edgeid e) {
68  double diff = solutions[e][u] - solutions[e][v];
69  scoreData[e] = fabs(diff);
70  });
71 
72  hasRun = true;
73 }
74 
75 template<class Matrix>
77  const count n = G.numberOfNodes();
78  const count m = G.numberOfEdges();
79  scoreData.clear();
80  scoreData.resize(m, 0.0);
81  double epsilon2 = tol * tol;
82  const count k = ceil(log2(n)) / epsilon2;
83  double randTab[3] = {1.0/sqrt(k), -1.0/sqrt(k)};
84 
85  std::vector<Vector> yRows(k, Vector(n));
86  std::vector<Vector> zRows(k, Vector(n));
87 
88  G.forEdges([&](node u, node v, edgeweight w, index) {
89 #pragma omp parallel for
90  for (index i = 0; i < k; ++i) {
91  double rand = randTab[Aux::Random::integer(1)];
92  yRows[i][u] += w * rand;
93  yRows[i][v] -= w * rand;
94  }
95  });
96 
97 
98  Lamg<Matrix> lamg(1e-5);
99  lamg.setupConnected(Matrix::laplacianMatrix(this->G));
100  lamg.parallelSolve(yRows, zRows);
101 
102  this->G.parallelForEdges([&](node u, node v, edgeid e) {
103  double sqSum = 0.0;
104  for (index i = 0; i < k; ++i) {
105  double diff = (zRows[i][u] - zRows[i][v]);
106  sqSum += diff * diff;
107  }
108 
109  scoreData[e] = sqSum;
110  });
111 
112  hasRun = true;
113 }
114 
115 
116 } /* namespace NetworKit */
117 
118 
119 
120 #endif /* NETWORKIT_CPP_ALGEBRAIC_ALGORITHMS_ALGEBRAICSPANNINGEDGECENTRALITY_H_ */
index edgeid
Definition: Globals.h:25
uint64_t integer()
Definition: Random.cpp:64
void run() override
Compute spanning edge centrality exactly.
Definition: AlgebraicSpanningEdgeCentrality.h:48
AlgebraicSpanningEdgeCentrality(const Graph &graph, double tol=0.1)
Constructs an instance of the AlgebraicSpanningEdgeCentrality algorithm for the given Graph graph...
Definition: AlgebraicSpanningEdgeCentrality.h:30
void parallelSolve(const std::vector< Vector > &rhs, std::vector< Vector > &results, count maxConvergenceTime=5 *60 *1000, count maxIterations=std::numeric_limits< count >::max())
Compute the results for the matrix currently setup and the right-hand sides rhs.
Definition: Lamg.h:219
uint64_t index
Typedefs.
Definition: Globals.h:20
void setupConnected(const Matrix &laplacianMatrix)
Compute the multigrid hierarchy for te given Laplacian matrix laplacianMatrix.
Definition: Lamg.h:109
Implementation of Spanning edge centrality with algebraic notation.
Definition: AlgebraicSpanningEdgeCentrality.h:21
void runApproximation()
Approximate spanning edge centrality scores with the Johnson-Lindenstrauss transform.
Definition: AlgebraicSpanningEdgeCentrality.h:76
Abstract base class for centrality measures.
Definition: Centrality.h:20
uint64_t count
Definition: Globals.h:21
index node
Definition: Globals.h:23
The Vector class represents a basic vector with double coefficients.
Definition: Vector.h:25
Represents the interface to the Lean Algebraic Multigrid (LAMG) graph Laplacian linear solver by Oren...
Definition: Lamg.h:30
A graph (with optional weights) and parallel iterator methods.
Definition: Graph.h:79
double edgeweight
Definition: Globals.h:24