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.community; 033 034import java.util.HashMap; 035 036import org.graphstream.graph.Edge; 037import org.graphstream.graph.Graph; 038import org.graphstream.graph.Node; 039 040/** 041 * This class implements an improved community detection algorithm based on the 042 * epidemic label propagation paradigm the was presented by Leung <i>et al</i>. 043 * 044 * @reference I. X. Y. Leung, P. Hui, P. Lio`, and J. Crowcroft, “Towards Real- 045 * Time Community Detection in Large Networks,” Physical Review E 046 * (Statistical, Nonlinear, and Soft Matter Physics), vol. 79, no. 6, 047 * pp. 066 107+, 2009. 048 * 049 * @author Guillaume-Jean Herbiet 050 * 051 */ 052public class Leung extends EpidemicCommunityAlgorithm { 053 054 /** 055 * Name of the marker that is used to store weight of links on the graph 056 * that this algorithm is applied to. 057 */ 058 protected String weightMarker = "weight"; 059 060 /** 061 * Comparable node characteristic preference exponent 062 */ 063 protected double m = 0.1; 064 065 /** 066 * Hop attenuation factor 067 */ 068 protected double delta = 0.05; 069 070 public Leung() { 071 super(); 072 } 073 074 public Leung(Graph graph) { 075 super(graph); 076 } 077 078 public Leung(Graph graph, String marker) { 079 super(graph, marker); 080 } 081 082 /** 083 * Create a new Leung algorithm instance, attached to the specified graph, 084 * using the specified marker to store the community attribute, and the 085 * specified weightMarker to retrieve the weight attribute of graph edges. 086 * 087 * @param graph 088 * graph to which the algorithm will be applied 089 * @param marker 090 * community attribute marker 091 * @param weightMarker 092 * edge weight marker 093 */ 094 public Leung(Graph graph, String marker, String weightMarker) { 095 super(graph, marker); 096 this.weightMarker = weightMarker; 097 } 098 099 /** 100 * Create a new Leung algorithm instance, attached to the specified graph, 101 * using the default markers for the node community and edge weight 102 * attributes. Sets the preference exponent and hop attenuation factor to 103 * the given values. 104 * 105 * @param graph 106 * graph to which the algorithm will be applied 107 * @param m 108 * comparable function preference exponent value 109 * @param delta 110 * hop attenuation factor value 111 */ 112 public Leung(Graph graph, double m, double delta) { 113 super(graph); 114 setParameters(m, delta); 115 } 116 117 /** 118 * Create a new Leung algorithm instance, attached to the specified graph, 119 * using the specified marker to store the community attribute, and the 120 * default marker to retrieve the weight attribute of graph edges. Sets the 121 * preference exponent and hop attenuation factor to the given values. 122 * 123 * @param graph 124 * graph to which the algorithm will be applied 125 * @param marker 126 * community attribute marker 127 * @param m 128 * comparable function preference exponent value 129 * @param delta 130 * hop attenuation factor value 131 */ 132 public Leung(Graph graph, String marker, double m, double delta) { 133 super(graph, marker); 134 setParameters(m, delta); 135 } 136 137 /** 138 * Create a new Leung algorithm instance, attached to the specified graph, 139 * using the specified marker to store the community attribute, and the 140 * specified weightMarker to retrieve the weight attribute of graph edges. 141 * Sets the preference exponent and hop attenuation factor to the given 142 * values. 143 * 144 * @param graph 145 * graph to which the algorithm will be applied 146 * @param marker 147 * community attribute marker 148 * @param weightMarker 149 * edge weight marker 150 * @param m 151 * comparable function preference exponent value 152 * @param delta 153 * hop attenuation factor value 154 */ 155 public Leung(Graph graph, String marker, String weightMarker, double m, 156 double delta) { 157 super(graph, marker); 158 this.weightMarker = weightMarker; 159 setParameters(m, delta); 160 } 161 162 /** 163 * Sets the preference exponent and hop attenuation factor to the given 164 * values. 165 * 166 * @param m 167 * comparable function preference exponent value 168 * @param delta 169 * hop attenuation factor value 170 */ 171 public void setParameters(double m, double delta) { 172 this.m = m; 173 this.delta = delta; 174 } 175 176 @Override 177 public void computeNode(Node node) { 178 /* 179 * Recall and update the node current community and previous score 180 */ 181 Object previousCommunity = node.getAttribute(marker); 182 Double previousScore = (Double) node.getAttribute(marker + ".score"); 183 super.computeNode(node); 184 185 /* 186 * Update the node label score 187 */ 188 189 // Handle first iteration 190 if (previousCommunity == null) { 191 previousCommunity = node.getAttribute(marker); 192 previousScore = (Double) node.getAttribute(marker + ".score"); 193 } 194 195 /* 196 * The node is the originator of the community and hasn't changed 197 * community at this iteration (or we are at the first simulation step): 198 * keep the maximum label score 199 */ 200 if ((node.getAttribute(marker).equals(previousCommunity)) 201 && (previousScore.equals(1.0))) 202 node.setAttribute(marker + ".score", 1.0); 203 204 /* 205 * Otherwise search for the highest score amongst neighbors and reduce 206 * it by decreasing factor 207 */ 208 else { 209 Double maxLabelScore = Double.NEGATIVE_INFINITY; 210 for (Edge e : node.getEnteringEdgeSet()) { 211 Node v = e.getOpposite(node); 212 if (v.hasAttribute(marker) 213 && v.getAttribute(marker).equals( 214 node.getAttribute(marker))) { 215 if ((Double) v.getAttribute(marker + ".score") > maxLabelScore) 216 maxLabelScore = (Double) v.getAttribute(marker 217 + ".score"); 218 } 219 } 220 node.setAttribute(marker + ".score", maxLabelScore - delta); 221 } 222 } 223 224 /** 225 * Compute the scores for all relevant communities for the selected node 226 * using Leung algorithm. 227 * 228 * @param u 229 * The node for which the scores computation is performed 230 * @complexity O(DELTA) where DELTA is is the average node degree in the 231 * network 232 */ 233 @Override 234 protected void communityScores(Node u) { 235 /* 236 * Reset the scores for each communities 237 */ 238 communityScores = new HashMap<Object, Double>(); 239 240 /* 241 * Iterate over the nodes that this node "hears" 242 */ 243 for (Edge e : u.getEnteringEdgeSet()) { 244 Node v = e.getOpposite(u); 245 246 /* 247 * Update the count for this community 248 */ 249 if (v.hasAttribute(marker)) { 250 251 // Compute the neighbor node current score 252 Double score = (Double) v.getAttribute(marker + ".score") 253 * Math.pow(v.getInDegree(), m); 254 255 /* 256 * The rest of the formula depends on the weighted status of the 257 * network 258 */ 259 Double weight; 260 if (e.hasAttribute(weightMarker)) 261 if (e.isDirected()) { 262 Edge e2 = v.getEdgeToward(u.getId()); 263 if (e2 != null && e2.hasAttribute(weightMarker)) 264 weight = (Double) e.getAttribute(weightMarker) 265 + (Double) e2.getAttribute(weightMarker); 266 else 267 weight = (Double) e.getAttribute(weightMarker); 268 } else 269 weight = (Double) e.getAttribute(weightMarker); 270 else 271 weight = 1.0; 272 273 // Update the score of the according community 274 if (communityScores.get(v.getAttribute(marker)) == null) 275 communityScores.put(v.getAttribute(marker), score * weight); 276 else 277 communityScores.put(v.getAttribute(marker), 278 communityScores.get(v.getAttribute(marker)) 279 + (score * weight)); 280 } 281 } 282 } 283 284 @Override 285 protected void originateCommunity(Node node) { 286 super.originateCommunity(node); 287 288 // Correct the original community score for the Leung algorithm 289 node.setAttribute(marker + ".score", 1.0); 290 } 291}