001/* 002 * Copyright 2006 - 2013 003 * Stefan Balev <stefan.balev@graphstream-project.org> 004 * Julien Baudry <julien.baudry@graphstream-project.org> 005 * Antoine Dutot <antoine.dutot@graphstream-project.org> 006 * Yoann Pigné <yoann.pigne@graphstream-project.org> 007 * Guilhelm Savin <guilhelm.savin@graphstream-project.org> 008 * 009 * This file is part of GraphStream <http://graphstream-project.org>. 010 * 011 * GraphStream is a library whose purpose is to handle static or dynamic 012 * graph, create them from scratch, file or any source and display them. 013 * 014 * This program is free software distributed under the terms of two licenses, the 015 * CeCILL-C license that fits European law, and the GNU Lesser General Public 016 * License. You can use, modify and/ or redistribute the software under the terms 017 * of the CeCILL-C license as circulated by CEA, CNRS and INRIA at the following 018 * URL <http://www.cecill.info> or under the terms of the GNU LGPL as published by 019 * the Free Software Foundation, either version 3 of the License, or (at your 020 * option) any later version. 021 * 022 * This program is distributed in the hope that it will be useful, but WITHOUT ANY 023 * WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A 024 * PARTICULAR PURPOSE. See the GNU Lesser General Public License for more details. 025 * 026 * You should have received a copy of the GNU Lesser General Public License 027 * along with this program. If not, see <http://www.gnu.org/licenses/>. 028 * 029 * The fact that you are presently reading this means that you have had 030 * knowledge of the CeCILL-C and LGPL licenses and that you accept their terms. 031 */ 032package org.graphstream.algorithm.measure; 033 034import java.util.Arrays; 035 036import org.graphstream.graph.Edge; 037import org.graphstream.graph.Node; 038 039public class EigenvectorCentrality extends AbstractCentrality { 040 public static final String DEFAULT_ATTRIBUTE_KEY = "eigenvector"; 041 042 public static final int DEFAULT_MAX_ITER = 100; 043 044 protected int maxIter; 045 protected String weightAttribute; 046 047 public EigenvectorCentrality() { 048 this("DEFAULT_ATTRIBUTE_KEY", NormalizationMode.NONE); 049 } 050 051 public EigenvectorCentrality(String attribute, NormalizationMode normalize) { 052 this(attribute, normalize, DEFAULT_MAX_ITER, "weight"); 053 } 054 055 public EigenvectorCentrality(String attribute, NormalizationMode normalize, 056 int maxIter, String weightAttribute) { 057 super(attribute, normalize); 058 059 this.maxIter = maxIter; 060 this.weightAttribute = weightAttribute; 061 } 062 063 @Override 064 protected void computeCentrality() { 065 int n = graph.getNodeCount(); 066 double[] x1 = new double[n]; 067 double[] x2 = new double[n]; 068 double[] t; 069 double f, s; 070 int iter = maxIter; 071 Node node; 072 Edge edge; 073 074 Arrays.fill(x2, 1.0 / n); 075 076 while (iter-- > 0) { 077 // 078 // Swap x1 and x2 079 // 080 t = x1; 081 x1 = x2; 082 x2 = t; 083 084 Arrays.fill(x2, 0); 085 s = 0; 086 087 for (int idx = 0; idx < n; idx++) { 088 node = graph.getNode(idx); 089 090 for (int i = 0; i < node.getDegree(); i++) { 091 edge = node.getEdge(i); 092 f = 1; 093 094 if (edge.hasNumber(weightAttribute)) 095 f = edge.getNumber(weightAttribute); 096 097 x2[idx] += x1[edge.getOpposite(node).getIndex()] * f; 098 } 099 100 s += x2[idx] * x2[idx]; 101 } 102 103 s = s == 0 ? 1.0 : 1.0 / Math.sqrt(s); 104 for (int idx = 0; idx < n; idx++) 105 x2[idx] *= s; 106 } 107 108 data = x2; 109 } 110 111}