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 the synchronous version of the 042 * "Epidemic Community Detection Algorithm" as presented by Raghavan <i>et 043 * al</i>. 044 * 045 * @reference U. N. Raghavan, R. Albert, and S. Kumara, “Near Linear Time Al- 046 * gorithm to Detect Community Structures in Large-scale Networks,” 047 * Physical Review E (Statistical, Nonlinear, and Soft Matter 048 * Physics), vol. 76, no. 3, 2007. 049 * 050 * @author Guillaume-Jean Herbiet 051 * 052 */ 053public class SyncEpidemicCommunityAlgorithm extends EpidemicCommunityAlgorithm { 054 055 /** 056 * Identify the current iteration of this algorithm to ensure synchronous 057 * behavior. 058 */ 059 protected int iteration = 0; 060 061 public SyncEpidemicCommunityAlgorithm() { 062 super(); 063 } 064 065 public SyncEpidemicCommunityAlgorithm(Graph graph) { 066 super(graph); 067 } 068 069 public SyncEpidemicCommunityAlgorithm(Graph graph, String marker) { 070 super(graph, marker); 071 } 072 073 @Override 074 public void terminate() { 075 iteration = 0; 076 } 077 078 @Override 079 public void compute() { 080 super.compute(); 081 iteration++; 082 } 083 084 @Override 085 public void computeNode(Node node) { 086 087 /* 088 * Save the node community to previous 089 */ 090 if (node.hasAttribute(marker)) 091 node.setAttribute(marker + ".previous", node.getAttribute(marker)); 092 093 /* 094 * Perform same assignment as in asynchronous mode difference is in the 095 * redefinition of the communityScores() method 096 */ 097 super.computeNode(node); 098 099 /* 100 * Save the iteration at which the node was last updated 101 */ 102 node.setAttribute(marker + ".step", iteration); 103 } 104 105 @Override 106 protected void communityScores(Node u) { 107 /* 108 * Reset the scores for each communities 109 */ 110 communityScores = new HashMap<Object, Double>(); 111 112 /* 113 * Iterate over the nodes that this node "hears" 114 */ 115 for (Edge e : u.getEnteringEdgeSet()) { 116 Node v = e.getOpposite(u); 117 118 /* 119 * Update the count for this community 120 */ 121 if (v.hasAttribute(marker + ".step")) { 122 123 /* 124 * Set the marker based on the neighbor node current update 125 * status 126 */ 127 String syncMarker = marker; 128 int updateStep = ((Integer) v.getAttribute(marker + ".step")) 129 .intValue(); 130 131 /* 132 * The neighbor node has been updated for this step use the 133 * previous marker 134 */ 135 if (updateStep == iteration) { 136 syncMarker += ".previous"; 137 } 138 139 /* 140 * Update the community score based on the selected marker 141 */ 142 if (v.hasAttribute(syncMarker)) 143 if (communityScores.get(v.getAttribute(syncMarker)) == null) 144 communityScores.put(v.getAttribute(syncMarker), 1.0); 145 else 146 communityScores 147 .put(v.getAttribute(syncMarker), 148 communityScores.get(v 149 .getAttribute(syncMarker)) + 1.0); 150 } 151 } 152 } 153}