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; 035import java.util.TreeMap; 036 037import org.graphstream.graph.Edge; 038import org.graphstream.graph.Graph; 039import org.graphstream.graph.Node; 040 041/** 042 * This class implements the "Epidemic Community Detection Algorithm" as 043 * presented by Raghavan <i>et al</i>. It also serves as base class for all 044 * algorithms using the epidemic label propagation paradigm. 045 * 046 * @reference U. N. Raghavan, R. Albert, and S. Kumara, “Near Linear Time Al- 047 * gorithm to Detect Community Structures in Large-scale Networks,” 048 * Physical Review E (Statistical, Nonlinear, and Soft Matter 049 * Physics), vol. 76, no. 3, 2007. 050 * 051 * @author Guillaume-Jean Herbiet 052 * 053 */ 054public class EpidemicCommunityAlgorithm extends DecentralizedCommunityAlgorithm { 055 056 /** 057 * Heard communities and their associated scores 058 */ 059 protected HashMap<Object, Double> communityScores; 060 061 public EpidemicCommunityAlgorithm() { 062 super(); 063 } 064 065 public EpidemicCommunityAlgorithm(Graph graph) { 066 super(graph); 067 } 068 069 public EpidemicCommunityAlgorithm(Graph graph, String marker) { 070 super(graph, marker); 071 } 072 073 /** 074 * Perform computation of one iteration of the algorithm on a given node 075 * using the epidemic label propagation algorithm. 076 * 077 * @complexity k times the complexity of the communityScores() function, 078 * where k is the average number of neighboring communities. 079 * @param node 080 */ 081 @Override 082 public void computeNode(Node node) { 083 /* 084 * Compute the community scores for this node 085 */ 086 communityScores(node); 087 088 /* 089 * Search for the community with the highest score 090 */ 091 Object maxCommunity = null; 092 Double maxScore = Double.NEGATIVE_INFINITY; 093 094 TreeMap<Object, Double> scores = new TreeMap<Object, Double>( 095 communityScores); 096 for (Object c : scores.keySet()) { 097 Double s = communityScores.get(c); 098 099 if (s > maxScore || (s == maxScore && rng.nextDouble() >= 0.5)) { 100 maxCommunity = c; 101 maxScore = s; 102 } 103 } 104 105 /* 106 * Update the node community 107 */ 108 if (maxCommunity == null) 109 originateCommunity(node); 110 else { 111 node.setAttribute(marker, maxCommunity); 112 node.setAttribute(marker + ".score", maxScore); 113 } 114 } 115 116 /** 117 * Compute the scores for all relevant communities for the selected node 118 * using epidemic label propagation paradigm. 119 * 120 * @param u 121 * The node for which the scores computation is performed 122 * @complexity O(DELTA) where DELTA is is the average node degree in the 123 * network 124 */ 125 protected void communityScores(Node u) { 126 /* 127 * Reset the scores for each communities 128 */ 129 communityScores = new HashMap<Object, Double>(); 130 131 /* 132 * Iterate over the nodes that this node "hears" 133 */ 134 for (Edge e : u.getEnteringEdgeSet()) { 135 Node v = e.getOpposite(u); 136 137 /* 138 * Update the count for this community 139 */ 140 if (v.hasAttribute(marker)) 141 if (communityScores.get(v.getAttribute(marker)) == null) 142 communityScores.put(v.getAttribute(marker), 1.0); 143 else 144 communityScores.put(v.getAttribute(marker), 145 communityScores.get(v.getAttribute(marker)) + 1.0); 146 } 147 } 148 149 @Override 150 protected void originateCommunity(Node node) { 151 super.originateCommunity(node); 152 node.setAttribute(marker + ".score", 0.0); 153 } 154}