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 org.apache.commons.math.stat.descriptive.moment.*; 035 036/** 037 * Provides some statistical information on the size of current community 038 * assignment on the specified graph as it evolves. 039 * 040 * @author Guillaume-Jean Herbiet 041 * 042 */ 043public class CommunityDistribution extends CommunityMeasure { 044 045 /** 046 * Biggest community currently generated. 047 */ 048 protected Object biggestCommunity = null; 049 050 /** 051 * Smallest community currently generated. 052 */ 053 protected Object smallestCommunity = null; 054 055 /** 056 * Average size of the currently generated communities. 057 */ 058 protected float avgSize = 0; 059 060 /** 061 * Standard deviation of the size of currently generated communities. 062 */ 063 protected float stdevSize = 0; 064 065 /** 066 * New size distribution measure using the specified marker as attribute 067 * name for the community assignment. 068 * 069 * @param marker 070 * Attribute name for the community assignment. 071 */ 072 public CommunityDistribution(String marker) { 073 super(marker); 074 } 075 076 @Override 077 /** 078 * Computes and update the statistical information on size distribution. 079 * 080 * @complexity O(C), where C is the expected number of communities. 081 */ 082 public void compute() { 083 if (graphChanged) { 084 // Default measure is the number of communities 085 M = (float) communities.size(); 086 087 // Update the smallest/biggest community 088 // and creates the size distribution 089 int maxSize = 0; 090 int minSize = Integer.MAX_VALUE; 091 092 double[] distribution = new double[(int) M]; 093 int k = 0; 094 Mean mean = new Mean(); 095 StandardDeviation stdev = new StandardDeviation(); 096 097 for (Object c : communities.keySet()) { 098 distribution[k++] = (communities.get(c)).size(); 099 100 if ((communities.get(c)).size() > maxSize) { 101 biggestCommunity = c; 102 maxSize = (communities.get(c)).size(); 103 } 104 if ((communities.get(c)).size() < minSize) { 105 smallestCommunity = c; 106 minSize = (communities.get(c)).size(); 107 } 108 } 109 110 // Compute the statistical moments 111 avgSize = (float) mean.evaluate(distribution); 112 stdevSize = (float) stdev.evaluate(distribution); 113 114 graphChanged = false; 115 } 116 } 117 118 /** 119 * Get the number of communities 120 * 121 * @return an int representing the current number of communities 122 */ 123 public int number() { 124 return (int) M; 125 } 126 127 /** 128 * Get the biggest generated community 129 * 130 * @return the biggest community 131 */ 132 public Object biggestCommunity() { 133 return biggestCommunity; 134 } 135 136 /** 137 * Get the smallest generated community 138 * 139 * @return the smallest community 140 */ 141 public Object smallestCommunity() { 142 return smallestCommunity; 143 } 144 145 /** 146 * Get the maximum community size 147 * 148 * @return an int reflecting the size of the biggest community 149 */ 150 public int maxCommunitySize() { 151 if (communities.get(biggestCommunity) == null) 152 return 0; 153 else 154 return (communities.get(biggestCommunity)).size(); 155 } 156 157 /** 158 * Get the minimum community size 159 * 160 * @return an int reflecting the size of the smallest community 161 */ 162 public int minCommunitySize() { 163 if (communities.get(smallestCommunity) == null) 164 return 0; 165 else 166 return (communities.get(smallestCommunity)).size(); 167 } 168 169 /** 170 * Compute the average community size 171 * 172 * @return Average community size 173 */ 174 public float average() { 175 return avgSize; 176 } 177 178 /** 179 * Compute the standard deviation of the community size 180 * 181 * @return Standard deviation of the community size 182 */ 183 public float stdev() { 184 return stdevSize; 185 } 186 187 /** 188 * Updates the distribution information and returns a string for an easy 189 * display of the results. 190 * 191 * The string has the following format: [number of communities] [average 192 * size] [stdev size] [min size] ([smallest community]) [max size] ([biggest 193 * community]) 194 * 195 * @return a String containing all computed distribution information. 196 */ 197 @Override 198 public String toString() { 199 compute(); 200 return (int) M + " " + avgSize + " " + stdevSize + " " 201 + minCommunitySize() + " (" + smallestCommunity + ") " 202 + maxCommunitySize() + " (" + biggestCommunity + ")"; 203 } 204 205}