fastcommunity_mh.cc

大型复杂网络社区划分的快速算法

////////////////////////////////////////////////////////////////////////
// --- COPYRIGHT NOTICE ---------------------------------------------
// FastCommunityMH - infers community structure of networks
// Copyright (C) 2004 Aaron Clauset
//
// This program is free software; you can redistribute it and/or modify
// it under the terms of the GNU General Public License as published by
// the Free Software Foundation; either version 2 of the License, or
// (at your option) any later version.
//
// This program is distributed in the hope that it will be useful,
// but WITHOUT ANY WARRANTY; without even the implied warranty of
// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
// GNU General Public License for more details.
//
// You should have received a copy of the GNU General Public License
// along with this program; if not, write to the Free Software
// Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
// 
// See http://www.gnu.org/licenses/gpl.txt for more details.
// 
////////////////////////////////////////////////////////////////////////
// Author       : Aaron Clauset  ([e-mail])				//
// Location     : U. Michigan, U. New Mexico						//
// Time         : January-August 2004							//
// Collaborators: Dr. Cris Moore ([e-mail])				//
//              : Dr. Mark Newman ([e-mail])				//
////////////////////////////////////////////////////////////////////////
// --- DEEPER DESCRIPTION ---------------------------------------------
//  see http://www.arxiv.org/abs/cond-mat/0408187 for more information
// 
//  - read network structure from data file (see below for constraints)
//  - builds dQ, H and a data structures
//  - runs new fast community structure inference algorithm
//  - records Q(t) function to file
//  - (optional) records community structure (at t==cutstep)
//  - (optional) records the list of members in each community (at t==cutstep)
//
////////////////////////////////////////////////////////////////////////
// --- PROGRAM USAGE NOTES ---------------------------------------------
// This program is rather complicated and requires a specific kind of input,
// so some notes on how to use it are in order. Mainly, the program requires
// a specific structure input file (.pairs) that has the following characteristics:
//  
//  1. .pairs is a list of tab-delimited pairs of numeric indices, e.g.,
//		"54\t91\n"
//  2. the network described is a SINGLE COMPONENT
//  3. there are NO SELF-LOOPS or MULTI-EDGES in the file; you can use
//     the 'netstats' utility to extract the giantcomponent (-gcomp.pairs)
//     and then use that file as input to this program
//  4. the MINIMUM NODE ID = 0 in the input file; the maximum can be
//     anything (the program will infer it from the input file)
// 
// Description of commandline arguments
// -f <filename>    give the target .pairs file to be processed
// -l <text>		the text label for this run; used to build output filenames
// -t <int>		timer period for reporting progress of file input to screen
// -s			calculate and record the support of the dQ matrix
// -v --v ---v		differing levels of screen output verbosity
// -o <directory>   directory for file output
// -c <int>		record the aglomerated network at step <int>
// 
////////////////////////////////////////////////////////////////////////
// Change Log:
// 2006-02-06: 1) modified readInputFile to be more descriptive of its actions
//             2) removed -o functionality; program writes output to directory
//             of input file. (also removed -h option of command line)
// 2006-10-13: 3) Janne Aukia ([e-mail]) suggested changes to the 
//             mergeCommunities() function here (see comments in that function),
//             and an indexing adjustment in printHeapTop10() in maxheap.h.
//
////////////////// //////////////////////////////////////////////////////

#include <iostream.h>
#include <fstream>
#include <string>
#include "stdlib.h"
#include "time.h"
#include "math.h"

#include "maxheap.h"
#include "vektor.h"

using namespace std;

// ------------------------------------------------------------------------------------
// Edge object - defined by a pair of vertex indices and *edge pointer to next in linked-list
class edge {
public:
	int     so;					// originating node
	int     si;					// terminating node
	edge    *next;					// pointer for linked list of edges
	
	edge();						// default constructor
	~edge();						// default destructor
};
edge::edge()  { so = 0; si = 0; next = NULL; }
edge::~edge() {}

// ------------------------------------------------------------------------------------
// Nodenub object - defined by a *node pointer and *node pointer 
struct nodenub {
	tuple	*heap_ptr;			// pointer to node(max,i,j) in max-heap of row maxes
	vektor    *v;					// pointer stored vector for (i,j)
};

// ------------------------------------------------------------------------------------
// tuple object - defined by an real value and (row,col) indices
#if !defined(TUPLE_INCLUDED)
#define TUPLE_INCLUDED
struct tuple {
	double    m;					// stored value
	int		i;					// row index
	int		j;					// column index
	int		k;					// heap index
};
#endif

// ordered pair structures (handy in the program)
struct apair { int x; int y; };
#if !defined(DPAIR_INCLUDED)
#define DPAIR_INCLUDED
class dpair {
public:
	int x; double y; dpair *next;
	dpair(); ~dpair();
};
dpair::dpair()  { x = 0; y = 0.0; next = NULL; }
dpair::~dpair() {}
#endif

// ------------------------------------------------------------------------------------
// List object - simple linked list of integers
class list {
public:
	int		index;				// node index
	list		*next;				// pointer to next element in linked list
	list();   ~list();
};
list::list()  { index= 0; next = NULL; }
list::~list() {}

// ------------------------------------------------------------------------------------
// Community stub object - stub for a community list
class stub {
public:
	bool		valid;				// is this community valid?
	int		size;				// size of community
	list		*members;				// pointer to list of community members
	list		*last;				// pointer to end of list
	stub();   ~stub();
};
stub::stub()  { valid = false; size = 0; members = NULL; last = NULL; }
stub::~stub() {
	list *current;
	if (members != NULL) {
		current = members;
		while (current != NULL) { members = current->next; delete current; current = members; }
	}
}

// ------------------------------------------------------------------------------------
// FUNCTION DECLARATIONS --------------------------------------------------------------

void buildDeltaQMatrix();
void buildFilenames();
void dqSupport();
void groupListsSetup();
void groupListsStats();
void groupListsUpdate(const int x, const int y);
void mergeCommunities(int i, int j);
bool parseCommandLine(int argc,char * argv[]);
void readInputFile();
void recordGroupLists();
void recordNetwork();

// ------------------------------------------------------------------------------------
// PROGRAM PARAMETERS -----------------------------------------------------------------

struct netparameters {
	int			n;				// number of nodes in network
	int			m;				// number of edges in network
	int			maxid;			// maximum node id
	int			minid;			// minimum node id
}; netparameters    gparm;

struct groupstats {
	int			numgroups;		// number of groups
	double		meansize;			// mean size of groups
	int			maxsize;			// size of largest group
	int			minsize;			// size of smallest group
	double		*sizehist;		// distribution of sizes
}; groupstats		gstats;

struct outparameters {
	short int		textFlag;			// 0: no console output
								// 1: writes file outputs
	bool			suppFlag;			// T: no support(t) file
								// F: yes support(t) file
	short int		fileFlag;			// 
	string		filename;			// name of input file
	string		d_in;			// (dir ) directory for input file
	string		d_out;			// (dir ) director for output file
	string		f_parm;			// (file) parameters output
	string		f_input;			// (file) input data file
	string		f_joins;			// (file) community hierarchy
	string		f_support;		// (file) dQ support as a function of time
	string		f_net;			// (file) .wpairs file for .cutstep network
	string		f_group;			// (file) .list of indices in communities at .cutstep
	string		f_gstats;			// (file) distribution of community sizes at .cutstep
	string		s_label;			// (temp) text label for run
	string		s_scratch;		// (temp) text for building filenames
	int			timer;			// timer for displaying progress reports 
	bool			timerFlag;		// flag for setting timer
	int			cutstep;			// step at which to record aglomerated network
}; outparameters	ioparm;

// ------------------------------------------------------------------------------------
// ----------------------------------- GLOBAL VARIABLES -------------------------------

char		pauseme;
edge		*e;				// initial adjacency matrix (sparse)
edge		*elist;			// list of edges for building adjacency matrix
nodenub   *dq;				// dQ matrix
maxheap   *h;				// heap of values from max_i{dQ_ij}
double    *Q;				// Q(t)
dpair     Qmax;			// maximum Q value and the corresponding time t
double    *a;				// A_i
apair	*joins;			// list of joins
stub		*c;				// link-lists for communities

enum {NONE};

int    supportTot;
double supportAve;

// ------------------------------------------------------------------------------------
// ----------------------------------- MAIN PROGRAM -----------------------------------
int main(int argc,char * argv[]) {

	// default values for parameters which may be modified from the commandline
	ioparm.timer     = 20;
	ioparm.fileFlag  = NONE;
	ioparm.suppFlag  = false;
	ioparm.textFlag  = 0;
	ioparm.filename  = "community.pairs";
	ioparm.s_label   = "a";
	time_t t1;	t1 = time(&t1);
	time_t t2;	t2 = time(&t2);
	
	// ----------------------------------------------------------------------
	// Parse the command line, build filenames and then import the .pairs file
	cout << "\nFast Community Inference.\n";
	cout << "Copyright (c) 2004 by Aaron Clauset ([e-mail])\n";
	if (parseCommandLine(argc, argv)) {} else { return 0; }
	cout << "\nimporting: " << ioparm.filename << endl;    // note the input filename
	buildFilenames();								// builds filename strings
	readInputFile();								// gets adjacency matrix data
	
	// ----------------------------------------------------------------------
	// Allocate data structures for main loop
	a     = new double [gparm.maxid];
	Q     = new double [gparm.n+1];
	joins = new apair  [gparm.n+1];
	for (int i=0; i<gparm.maxid; i++) { a[i] = 0.0; }
	for (int i=0; i<gparm.n+1;   i++) { Q[i] = 0.0; joins[i].x = 0; joins[i].y = 0; }
	int t = 1;
	Qmax.y = -4294967296.0;  Qmax.x = 0;
	if (ioparm.cutstep > 0) { groupListsSetup(); }		// will need to track agglomerations
	
	cout << "now building initial dQ[]" << endl;
	buildDeltaQMatrix();							// builds dQ[] and h
	
	// initialize f_joins, f_support files
	ofstream fjoins(ioparm.f_joins.c_str(), ios::trunc);
	fjoins << -1 << "\t" << -1 << "\t" << Q[0] << "\t0\n";
	fjoins.close();

	if (ioparm.suppFlag) {
		ofstream fsupp(ioparm.f_support.c_str(), ios::trunc);
		dqSupport();
		fsupp << 0 << "\t" << supportTot << "\t" << supportAve << "\t" << 0 << "\t->\t" << 0 << "\n";
		fsupp.close();
	}
	
	// ----------------------------------------------------------------------
	// Start FastCommunity algorithm
	cout << "starting algorithm now." << endl;
	tuple  dQmax, dQnew;
	int isupport, jsupport;
	while (h->heapSize() > 2) {