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 static org.graphstream.algorithm.Toolkit.modularity; 035import static org.graphstream.algorithm.Toolkit.modularityMatrix; 036 037/** 038 * Computes and updates the modularity of a given graph as it evolves. 039 * 040 * @reference M. E. Newman and M. Girvan, “Finding and Evaluating Community 041 * Structure in Networks,” <i>Physical Review E (Statistical, 042 * Nonlinear, and Soft Matter Physics)</i>, vol. 69, no. 2, pp. 026 043 * 113+, Feb 2004. 044 * 045 * @author Yoann Pigné 046 * @author Guillaume-Jean Herbiet 047 */ 048public class Modularity extends CommunityMeasure { 049 050 /** 051 * Possible weighted extension for the modularity computation 052 */ 053 protected String weightMarker = null; 054 055 /** 056 * New modularity algorithm using the default marker for communities and no 057 * weight on edges. 058 */ 059 public Modularity() { 060 super("community"); 061 } 062 063 /** 064 * New modularity algorithm with a given marker for communities and no 065 * weight on edges. 066 * 067 * @param marker 068 * name of the attribute marking the communities. 069 */ 070 public Modularity(String marker) { 071 super(marker); 072 } 073 074 /** 075 * New weighted modularity algorithm with a given marker for communities and 076 * the given weightMarker for edge weights. 077 * 078 * @param marker 079 * name of the attribute marking the communities. 080 * @param weightMarker 081 * name of the attribute marking the weight of edges. 082 */ 083 public Modularity(String marker, String weightMarker) { 084 super(marker); 085 this.weightMarker = weightMarker; 086 } 087 088 /** 089 * Enables weighted extension of the modularity using the given weightMarker 090 * for edge weights. 091 * 092 * @param weightMarker 093 * name of the attribute marking the weight of edges. 094 */ 095 public void setWeightMarker(String weightMarker) { 096 this.weightMarker = weightMarker; 097 } 098 099 /* 100 * (non-Javadoc) 101 * 102 * @see org.graphstream.algorithm.Algorithm#compute() 103 */ 104 /** 105 * @complexity O(n+m!+m!k) 106 */ 107 @Override 108 public void compute() { 109 if (graphChanged) { 110 double[][] E = modularityMatrix(graph, communities, weightMarker); 111 M = modularity(E); 112 graphChanged = false; 113 } 114 } 115}