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.
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. |
/* * Copyright (C) 2013 - 2020 Oracle and/or its affiliates. All rights reserved. */ 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; diff.reduceAdd(abs(ec.get(n) - val)); ec.set(n, val); }); iter++; } while ((iter < maxIter) && (diff.get() > maxDiff)); } }
/* * Copyright (C) 2013 - 2020 Oracle and/or its affiliates. All rights reserved. */ 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)); }