You signed in with another tab or window. Reload to refresh your session.You signed out in another tab or window. Reload to refresh your session.You switched accounts on another tab or window. Reload to refresh your session.Dismiss alert
I have a question about PageRank algorithm, I made some modification on this algorithm to serve my needs, but the ranks are different from your PageRank, I checked your code but I couldn't find the key difference logically, and here is my implementation. I hope you can advice me with any help.
Here is my code:
public class PageRankV2 {
private final double[][] adjMatrix;
private final double[] assetLossVec;
private final HashMap<Integer, HashMap<Integer, Integer>> mapNodeToParent;
private final int numberOfNodes;
private final int maxIter;
private final double Wf;
private final double dampingFactor;
private final float ebsilon;
/**
* This constructor is used to initialize the adjacency matrix that is going to be passed to page rank
* @param adjMatrix The adjacency matrix which represents the attack-defence graph
* @param lossVector The assets' loss values as a vector
* @param maxIteration The number of iteration to keep ranking the nodes
* @param weightFactor The weight factor which is relied on in [0,1]
*/
public PageRankV2(double[][] adjMatrix, double[] lossVector, int maxIteration, double weightFactor) {
if (adjMatrix == null) {
throw new IllegalArgumentException("The matrix is null!");
}
if (lossVector == null) {
throw new IllegalArgumentException("The loss vector is null");
}
if (maxIteration < 0) {
throw new IllegalArgumentException("The number of iteration should be positive integer");
}
if (weightFactor < 0 || weightFactor > 1) {
throw new IllegalArgumentException("The weight factor should be relied in 0 and 1");
}
this.adjMatrix = adjMatrix;
this.assetLossVec = lossVector;
this.maxIter = maxIteration;
this.Wf = weightFactor;
this.dampingFactor = 0.85;
this.ebsilon = 0.0001F;
this.numberOfNodes = adjMatrix.length;
this.mapNodeToParent = new HashMap<>();
IntStream.range(0, numberOfNodes).forEach(nod -> mapNodeToParent.put(nod + 1, new HashMap<>()));
}
public HashMap<Integer, Double> startRanking() {
HashMap<Integer, Double> mapNodeToRank = new HashMap<>();
HashMap<Integer, Double> oldRanks = new HashMap<>();
IntStream.range(0, numberOfNodes).forEach(nod -> mapNodeToRank.put(nod + 1, 1.0 / numberOfNodes));
for (int iter = 0; iter < maxIter; iter++) {
for (int nod : mapNodeToRank.keySet()) {
// We get the parents (in edges) of the current node
var parents = getInDegree(nod);
// We get the number of incoming edges for each parent node of the given nod
for (Integer parent : parents) {
mapNodeToParent.get(nod).put(parent, getInDegree(parent).size());
}
// Hold the parents of the given nod and if they don't have incoming nodes, then do what inside the if statement
HashMap<Integer, Integer> givenNode = mapNodeToParent.get(nod);
if (givenNode.isEmpty()) {
mapNodeToRank.put(nod, (1 - dampingFactor) / numberOfNodes + Wf * assetLossVec[nod - 1]);
} else { // If the parents of the given nod have parents then do the following
double totalRank = 0d;
for (Map.Entry<Integer, Integer> incomeNode : givenNode.entrySet()) {
int currentNode = incomeNode.getKey();
double sumOfOutEdgesWeights = getSumOfOutEdges(currentNode);
double weightOfInDegreeEdges = Math.exp(-adjMatrix[currentNode - 1][nod - 1]);
totalRank += weightOfInDegreeEdges * mapNodeToRank.get(currentNode) / sumOfOutEdgesWeights;
}
totalRank = (1 - dampingFactor) / numberOfNodes + dampingFactor * totalRank + Wf * assetLossVec[nod - 1];
mapNodeToRank.put(nod, totalRank);
}
}
if (iter == 1) {
oldRanks.putAll(mapNodeToRank);
} else if (iter > 1) {
double sumOfSubtraction = 0d;
for (int key : oldRanks.keySet()) {
sumOfSubtraction += Math.pow(oldRanks.get(key) - mapNodeToRank.get(key), 2);
}
if (Math.sqrt(sumOfSubtraction) < ebsilon) {
break;
}
}
}
// Normalizing the ranks of nodes
double sumOfAllRanks = mapNodeToRank.values().stream().mapToDouble(value -> value).sum();
mapNodeToRank.replaceAll((n, v) -> mapNodeToRank.get(n) / sumOfAllRanks);
return mapNodeToRank;
}
private ArrayList<Integer> getInDegree(int node) {
ArrayList<Integer> parentsNodes = new ArrayList<>();
for (int i = 0; i < adjMatrix.length; i++) {
if (adjMatrix[i][node - 1] > 0) {
parentsNodes.add(i + 1);
}
}
return parentsNodes;
}
private double getSumOfOutEdges(int node) {
double sumOfWeights = 0d;
for (int i = 0; i < adjMatrix.length; i++) {
if (adjMatrix[node - 1][i] > 0) {
sumOfWeights += Math.exp(-adjMatrix[node - 1][i]);
}
}
return sumOfWeights;
}
public HashMap<Integer, Double> getScores() {
HashMap<Integer, Double> ranks = startRanking();
HashMap<Integer, Double> scores = new HashMap<>();
for (int node = 0; node < assetLossVec.length; node++) {
if (assetLossVec[node] > 0) {
scores.put(node, ranks.get(node));
}
}
double totalSumOfRanks = scores.values().stream().mapToDouble(Double::doubleValue).sum();
for (Integer key : scores.keySet()) {
scores.replace(key, scores.get(key) / totalSumOfRanks);
}
return scores;
}
}
The text was updated successfully, but these errors were encountered:
Dear,
I have a question about PageRank algorithm, I made some modification on this algorithm to serve my needs, but the ranks are different from your PageRank, I checked your code but I couldn't find the key difference logically, and here is my implementation. I hope you can advice me with any help.
Here is my code:
}
The text was updated successfully, but these errors were encountered: