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}