PGX 21.1.1
Documentation

## Eigenvector Centrality

##### Categoryranking and walkingAlgorithm IDpgx_builtin_k6_eigenvector_centralityTime ComplexityO(V * k) with V = number of vertices, k <= maximum number of iterationsSpace RequirementO(2 * V) with V = number of verticesJavadocAnalyst#eigenvectorCentrality(PgxGraph graph) Analyst#eigenvectorCentrality(PgxGraph graph, int max, double maxDiff, boolean useL2Norm, boolean useInEdge) Analyst#eigenvectorCentrality(PgxGraph graph, int max, double maxDiff, boolean useL2Norm, boolean useInEdge, VertexProperty ec) Analyst#eigenvectorCentrality(PgxGraph graph, VertexProperty ec)

The Eigenvector Centrality determines the centrality of a vertex by adding and weighting the centrality of its neighbors. Using outgoing or incoming edges when computing the eigenvector centrality will be equivalent to do so with the normal or the transpose adjacency matrix, respectively leading to the "right" and "left" eigenvectors.

## Signature

Input Argument Type Comment
G graph
max_iter int maximum number of iterations that will be performed.
max_diff double maximum tolerated error value. The algorithm will stop once the sum of the error values of all vertices becomes smaller than this value.
use_l2norm boolean boolean flag to determine whether the algorithm will use the l2 norm (Euclidean norm) or the l1 norm (absolute value) to normalize the centrality scores.
use_inEdges boolean boolean flag to determine whether the algorithm will use the incoming or the outgoing edges in the graph for the computations.
Output Argument Type Comment
ec vertexProp vertex property holding the normalized centrality value for each vertex.

## Code

```/*
*/
package oracle.pgx.algorithms;

import oracle.pgx.algorithm.annotations.GraphAlgorithm;
import oracle.pgx.algorithm.PgxGraph;
import oracle.pgx.algorithm.Scalar;
import oracle.pgx.algorithm.VertexProperty;
import oracle.pgx.algorithm.annotations.Out;

import static java.lang.Math.abs;
import static java.lang.Math.sqrt;

@GraphAlgorithm
public class EigenvectorCentrality {
public void eigenvectorCentrality(PgxGraph g, int maxIter, double maxDiff, boolean useL2Norm, boolean useInedges,
@Out VertexProperty<Double> ec) {
VertexProperty<Double> ecUnnormal = VertexProperty.create();

// Initialize
ec.setAll(1.0 / (double) g.getNumVertices());

int iter = 0;
Scalar<Double> diff = Scalar.create();
diff.set(0.0);

do {
// compute unnormalized sum
g.getVertices().forEach(n -> {
if (useInedges) {
ecUnnormal.set(n, n.getInNeighbors().sum(ec));
} else {
ecUnnormal.set(n, n.getNeighbors().sum(ec));
}
});

double s;
if (useL2Norm) {
// L2 Norm Normalization
double l2Sum = g.getVertices().sum(n -> ecUnnormal.get(n) * ecUnnormal.get(n));
s = (l2Sum == 0) ? 1.0 : 1 / sqrt(l2Sum);
} else {
// L1 Norm Normalization
double l1Sum = g.getVertices().sum(n -> abs(ecUnnormal.get(n)));
s = (l1Sum == 0) ? 1.0 : 1 / (l1Sum);
}

// update for next step
diff.set(0.0);
g.getVertices().forEach(n -> {
double val = ecUnnormal.get(n) * s;
ec.set(n, val);
});
iter++;
} while ((iter < maxIter) && (diff.get() > maxDiff));
}
}
```
```/*
*/

procedure eigenvector_centrality(graph G, int max_iter, double max_diff, bool use_l2norm,
bool use_inEdges; vertexProp<double> ec) {

vertexProp<double> ec_unnormal;

// Initialize
G.ec = 1.0 / (double) G.numNodes();

int iter = 0;
double diff = 0.0;

do {
// compute unnormalized sum
foreach (n: G.nodes) {
if (use_inEdges)
n.ec_unnormal = sum (v: n.inNbrs) {v.ec};
else
n.ec_unnormal = sum (v: n.nbrs) {v.ec};
}

double s;
if (use_l2norm) {
// L2 Norm Normalization
double l2Sum = sum (n: G.nodes) {n.ec_unnormal * n.ec_unnormal};
s = (l2Sum == 0) ? 1.0 : 1 / sqrt(l2Sum);
} else {
// L1 Norm Normalization
double l1Sum = sum (n: G.nodes) {|n.ec_unnormal|};
s = (l1Sum == 0) ? 1.0 : 1 / (l1Sum);
}

// update for next step
diff = 0;
foreach (n: G.nodes) {
double val = n.ec_unnormal * s;
diff += |n.ec - val|;
n.ec = val;
}
iter++;

} while ((iter < max_iter) && (diff > max_diff));
}
```