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}