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
034public class VariationOfInformation extends NormalizedMutualInformation {
035
036        public VariationOfInformation(String marker) {
037                super(marker);
038        }
039
040        public VariationOfInformation(String marker, String referenceMarker) {
041                super(marker, referenceMarker);
042        }
043
044        @Override
045        /**
046         * B.Karrer, E.Levina and M.E.J.Newman, 
047         * RobustnessofCommunity Structure in Networks, 
048         * Physical Review E (Statistical, Nonlinear, and Soft Matter Physics), 
049         * vol. 77, no. 4, 2008.
050         */
051        public void compute() {
052                // Get the updated confusion matrix
053                int[][] N = confusionMatrix();
054
055                // Get the arrays of the rows and columns sums
056                int[] N_A = new int[referenceCommunities.size()];
057                int[] N_B = new int[communities.size()];
058                for (int i = 0; i < N_A.length; i++) {
059                        int ttl = 0;
060                        for (int j = 0; j < N_B.length; j++)
061                                ttl += N[i][j];
062                        N_A[i] = ttl;
063                }
064                for (int j = 0; j < N_B.length; j++) {
065                        int ttl = 0;
066                        for (int i = 0; i < N_A.length; i++)
067                                ttl += N[i][j];
068                        N_A[j] = ttl;
069                }
070
071                // Get the total nodes number
072                float n = graph.getNodeCount();
073
074                /*
075                 * Let's go and compute the NMI
076                 */
077                float voi = 0;
078
079                for (int i = 0; i < N_A.length; i++)
080                        for (int j = 0; j < N_B.length; j++)
081                                voi += N[i][j]
082                                                * (Math.log((float) N[i][j] / (float) N_B[j]) + Math
083                                                                .log((float) N[i][j] / (float) N_A[i]));
084                M = (-1 / n) * voi;
085
086        }
087
088}