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}