blob: da0c1a8fc1f1309b55fb0150232d80b5915ec83e (
plain)
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
|
package Chapter4.util;
import GraphElements.RetweetEdge;
import GraphElements.UserNode;
import cern.colt.matrix.DoubleMatrix2D;
import cern.colt.matrix.impl.SparseDoubleMatrix2D;
import cern.colt.matrix.linalg.EigenvalueDecomposition;
import edu.uci.ics.jung.algorithms.scoring.VertexScorer;
import edu.uci.ics.jung.graph.Hypergraph;
/**
* This is a Jung Node Scorer that computes the Eigenvector Centrality for each node.
*/
public class EigenVectorScorer implements VertexScorer<UserNode, Double> {
private UserNode[] users;
private DoubleMatrix2D eigenVectors;
private int dominantEigenvectorIdx;
public EigenVectorScorer(Hypergraph<UserNode, RetweetEdge> graph){
users = new UserNode[graph.getVertexCount()];
graph.getVertices().toArray(users);
/* Step 1: Create the adjacency matrix.
*
* An adjacency matrix is a matrix with N users and N columns,
* where N is the number of nodes in the network.
* An entry in the matrix is 1 when node i connects to node j,
* and 0 otherwise.
*/
SparseDoubleMatrix2D matrix = new SparseDoubleMatrix2D(users.length, users.length);
for(int i = 0; i < users.length; i++){
for(int j = 0; j < users.length; j++){
matrix.setQuick(i, j, graph.containsEdge(new RetweetEdge(users[i], users[j])) ? 1 : 0);
}
}
/* Step 2: Find the principle eigenvector.
* For more information on eigen-decomposition please see
* http://mathworld.wolfram.com/EigenDecomposition.html
*/
EigenvalueDecomposition eig = new EigenvalueDecomposition(matrix);
DoubleMatrix2D eigenVals = eig.getD();
eigenVectors = eig.getV();
dominantEigenvectorIdx = 0;
for(int i = 1; i < eigenVals.columns(); i++){
if(eigenVals.getQuick(dominantEigenvectorIdx, dominantEigenvectorIdx) <
eigenVals.getQuick(i, i)){
dominantEigenvectorIdx = i;
}
}
}
public Double getVertexScore(UserNode arg0) {
for(int i = 0; i < users.length; i++){
if(users[i].equals(arg0)){
return Math.abs(eigenVectors.getQuick(i, dominantEigenvectorIdx));
}
}
return null;
}
}
|