fastcommunity_mh.cc

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

}

// ------------------------------------------------------------------------------------

void groupListsUpdate(const int x, const int y) {
	
	c[y].last->next = c[x].members;				// attach c[y] to end of c[x]
	c[y].last		 = c[x].last;					// update last[] for community y
	c[y].size		 += c[x].size;					// add size of x to size of y
	
	c[x].members   = NULL;						// delete community[x]
	c[x].valid	= false;						// 
	c[x].size		= 0;							// 
	c[x].last		= NULL;						// delete last[] for community x
	
	return;
}

// ------------------------------------------------------------------------------------

void mergeCommunities(int i, int j) {
	
	// To do the join operation for a pair of communities (i,j), we must update the dQ
	// values which correspond to any neighbor of either i or j to reflect the change.
	// In doing this, there are three update rules (cases) to follow:
	//  1. jix-triangle, in which the community x is a neighbor of both i and j
	//  2. jix-chain, in which community x is a neighbor of i but not j
	//  3. ijx-chain, in which community x is a neighbor of j but not i
	//
	// For the first two cases, we may make these updates by simply getting a list of
	// the elements (x,dQ) of [i] and stepping through them. If x==j, then we can ignore
	// that value since it corresponds to an edge which is being absorbed by the joined
	// community (i,j). If [j] also contains an element (x,dQ), then we have a triangle;
	// if it does not, then we have a jix-chain.
	//
	// The last case requires that we step through the elements (x,dQ) of [j] and update each
	// if [i] does not have an element (x,dQ), since that implies a ijx-chain.
	// 
	// Let d([i]) be the degree of the vector [i], and let k = d([i]) + d([j]). The running
	// time of this operation is O(k log k)
	//
	// Essentially, we do most of the following operations for each element of
	// dq[i]_x where x \not= j
	//  1.  add dq[i]_x to dq[j]_x (2 cases)
	//  2.  remove dq[x]_i
	//  3.  update maxheap[x]
	//  4.  add dq[i]_x to dq[x]_j (2 cases)
	//  5.  remove dq[j]_i
	//  6.  update maxheap[j]
	//  7.  update a[j] and a[i]
	//  8.  delete dq[i]
	
	dpair *list, *current, *temp;
	tuple newMax;
	int t = 1;
	
	// -- Working with the community being inserted (dq[i])
	// The first thing we must do is get a list of the elements (x,dQ) in dq[i]. With this 
	// list, we can then insert each into dq[j].

	//	dq[i].v->printTree();
	list    = dq[i].v->returnTreeAsList();			// get a list of items in dq[i].v
	current = list;							// store ptr to head of list
	
	if (ioparm.textFlag>1) {
		cout << "stepping through the "<<dq[i].v->returnNodecount() << " elements of community " << i << endl;
	}
		
	// ---------------------------------------------------------------------------------
	// SEARCHING FOR JIX-TRIANGLES AND JIX-CHAINS --------------------------------------
	// Now that we have a list of the elements of [i], we can step through them to check if
	// they correspond to an jix-triangle, a jix-chain, or the edge (i,j), and do the appropriate
	// operation depending.
	
	while (current!=NULL) {						// insert list elements appropriately
		
		if (ioparm.textFlag>1) { cout << endl << "element["<<t<<"] from dq["<<i<<"] is ("<<current->x<<" "<<current->y<<")" << endl; }

		// If the element (x,dQ) is actually (j,dQ), then we can ignore it, since it will 
		// correspond to an edge internal to the joined community (i,j) after the join.
		if (current->x != j) {

			// Now we must decide if we have a jix-triangle or a jix-chain by asking if
			// [j] contains some element (x,dQ). If the following conditional is TRUE,
			// then we have a jix-triangle, ELSE it is a jix-chain.
			
			if (dq[j].v->findItem(current->x)) {
				// CASE OF JIX-TRIANGLE
				if (ioparm.textFlag>1) {
					cout << "  (0) case of triangle: e_{"<<current->x<<" "<<j<<"} exists" << endl;
					cout << "  (1) adding ("<<current->x<<" "<<current->y<<") to dq["<<current->x<<"] as ("<<j<<" "<<current->y<<")"<<endl;
				}
				
				// We first add (x,dQ) from [i] to [x] as (j,dQ), since [x] essentially now has
				// two connections to the joined community [j].
				if (ioparm.textFlag>1) {
					cout << "  (1) heapsize = " << dq[current->x].v->returnHeaplimit() << endl; 
					cout << "  (1) araysize = " << dq[current->x].v->returnArraysize() << endl; 
					cout << "  (1) vectsize = " << dq[current->x].v->returnNodecount() << endl; }
				dq[current->x].v->insertItem(j,current->y);			// (step 1)

				// Then we need to delete the element (i,dQ) in [x], since [i] is now a
				// part of [j] and [x] must reflect this connectivity.
				if (ioparm.textFlag>1) { cout << "  (2) now we delete items associated with "<< i << " in dq["<<current->x<<"]" << endl; }
				dq[current->x].v->deleteItem(i);					// (step 2)

				// After deleting an item, the tree may now have a new maximum element in [x],
				// so we need to check it against the old maximum element. If it's new, then
				// we need to update that value in the heap and reheapify.
				newMax = dq[current->x].v->returnMaxStored();		// (step 3)
				if (ioparm.textFlag>1) { cout << "  (3) and dq["<<current->x<<"]'s new maximum is (" << newMax.m <<" "<<newMax.j<< ") while the old maximum was (" << dq[current->x].heap_ptr->m <<" "<<dq[current->x].heap_ptr->j<<")"<< endl; }
//				if (newMax.m > dq[current->x].heap_ptr->m || dq[current->x].heap_ptr->j==i) {
					h->updateItem(dq[current->x].heap_ptr, newMax);
					if (ioparm.textFlag>1) { cout << "  updated dq["<<current->x<<"].heap_ptr to be (" << dq[current->x].heap_ptr->m <<" "<<dq[current->x].heap_ptr->j<<")"<< endl; }
//				}
// Change suggested by Janne Aukia ([e-mail]) on 12 Oct 2006
				
				// Finally, we must insert (x,dQ) into [j] to note that [j] essentially now
				// has two connections with its neighbor [x].
				if (ioparm.textFlag>1) { cout << "  (4) adding ("<<current->x<<" "<<current->y<<") to dq["<<j<<"] as ("<<current->x<<" "<<current->y<<")"<<endl; }
				dq[j].v->insertItem(current->x,current->y);		// (step 4)
				
			} else {
				// CASE OF JIX-CHAIN
				
				// The first thing we need to do is calculate the adjustment factor (+) for updating elements.
				double axaj = -2.0*a[current->x]*a[j];
				if (ioparm.textFlag>1) {
					cout << "  (0) case of jix chain: e_{"<<current->x<<" "<<j<<"} absent" << endl;
					cout << "  (1) adding ("<<current->x<<" "<<current->y<<") to dq["<<current->x<<"] as ("<<j<<" "<<current->y+axaj<<")"<<endl;
				}
				
				// Then we insert a new element (j,dQ+) of [x] to represent that [x] has
				// acquired a connection to [j], which was [x]'d old connection to [i]
				dq[current->x].v->insertItem(j,current->y + axaj);	// (step 1)
				
				// Now the deletion of the connection from [x] to [i], since [i] is now
				// a part of [j]
				if (ioparm.textFlag>1) { cout << "  (2) now we delete items associated with "<< i << " in dq["<<current->x<<"]" << endl; }
				dq[current->x].v->deleteItem(i);					// (step 2)
				
				// Deleting that element may have changed the maximum element for [x], so we
				// need to check if the maximum of [x] is new (checking it against the value
				// in the heap) and then update the maximum in the heap if necessary.
				newMax = dq[current->x].v->returnMaxStored();		// (step 3)
				if (ioparm.textFlag>1) { cout << "  (3) and dq["<<current->x<<"]'s new maximum is (" << newMax.m <<" "<<newMax.j<< ") while the old maximum was (" << dq[current->x].heap_ptr->m <<" "<<dq[current->x].heap_ptr->j<<")"<< endl; }
//				if (newMax.m > dq[current->x].heap_ptr->m || dq[current->x].heap_ptr->j==i) {
					h->updateItem(dq[current->x].heap_ptr, newMax);
					if (ioparm.textFlag>1) { cout << "  updated dq["<<current->x<<"].heap_ptr to be (" << dq[current->x].heap_ptr->m <<" "<<dq[current->x].heap_ptr->j<<")"<< endl; }
//				}
// Change suggested by Janne Aukia ([e-mail]) on 12 Oct 2006
					
				// Finally, we insert a new element (x,dQ+) of [j] to represent [j]'s new
				// connection to [x]
				if (ioparm.textFlag>1) { cout << "  (4) adding ("<<current->x<<" "<<current->y<<") to dq["<<j<<"] as ("<<current->x<<" "<<current->y+axaj<<")"<<endl; }
				dq[j].v->insertItem(current->x,current->y + axaj);	// (step 4)

			}    // if (dq[j].v->findItem(current->x))
			
		}    // if (current->x != j)
		
		temp    = current;
		current = current->next;						// move to next element
		delete temp;
		temp = NULL;
		t++;
	}    // while (current!=NULL)

	// We've now finished going through all of [i]'s connections, so we need to delete the element
	// of [j] which represented the connection to [i]
	if (ioparm.textFlag>1) {
		cout << endl;
		cout << "  whoops. no more elements for community "<< i << endl;
		cout << "  (5) now deleting items associated with "<<i<< " (the deleted community) in dq["<<j<<"]" << endl;
	}

	if (ioparm.textFlag>1) { dq[j].v->printTree(); }
	dq[j].v->deleteItem(i);						// (step 5)
	
	// We can be fairly certain that the maximum element of [j] was also the maximum
	// element of [i], so we need to check to update the maximum value of [j] that
	// is in the heap.
	newMax = dq[j].v->returnMaxStored();			// (step 6)
	if (ioparm.textFlag>1) { cout << "  (6) dq["<<j<<"]'s old maximum was (" << dq[j].heap_ptr->m <<" "<< dq[j].heap_ptr->j<< ")\t"<<dq[j].heap_ptr<<endl; }
	h->updateItem(dq[j].heap_ptr, newMax);
	if (ioparm.textFlag>1) { cout << "      dq["<<j<<"]'s new maximum  is (" << dq[j].heap_ptr->m <<" "<< dq[j].heap_ptr->j<< ")\t"<<dq[j].heap_ptr<<endl; }
	if (ioparm.textFlag>1) { dq[j].v->printTree(); }
	
	// ---------------------------------------------------------------------------------
	// SEARCHING FOR IJX-CHAINS --------------------------------------------------------
	// So far, we've treated all of [i]'s previous connections, and updated the elements
	// of dQ[] which corresponded to neighbors of [i] (which may also have been neighbors
	// of [j]. Now we need to update the neighbors of [j] (as necessary)
	
	// Again, the first thing we do is get a list of the elements of [j], so that we may
	// step through them and determine if that element constitutes an ijx-chain which
	// would require some action on our part.
	list = dq[j].v->returnTreeAsList();			// get a list of items in dq[j].v
	current = list;							// store ptr to head of list
	t       = 1;
	if (ioparm.textFlag>1) { cout << "\nstepping through the "<<dq[j].v->returnNodecount() << " elements of community " << j << endl; }

	while (current != NULL) {					// insert list elements appropriately
		if (ioparm.textFlag>1) { cout << endl << "element["<<t<<"] from dq["<<j<<"] is ("<<current->x<<" "<<current->y<<")" << endl; }

		// If the element (x,dQ) of [j] is not also (i,dQ) (which it shouldn't be since we've
		// already deleted it previously in this function), and [i] does not also have an
		// element (x,dQ), then we have an ijx-chain.
		if ((current->x != i) && (!dq[i].v->findItem(current->x))) {
			// CASE OF IJX-CHAIN
			
			// First we must calculate the adjustment factor (+).
			double axai = -2.0*a[current->x]*a[i];
			if (ioparm.textFlag>1) {
				cout << "  (0) case of ijx chain: e_{"<<current->x<<" "<<i<<"} absent" << endl;
				cout << "  (1) updating dq["<<current->x<<"] to ("<<j<<" "<<current->y+axai<<")"<<endl;
			}
			
			// Now we must add an element (j,+) to [x], since [x] has essentially now acquired
			// a new connection to [i] (via [j] absorbing [i]).
			dq[current->x].v->insertItem(j, axai);			// (step 1)

			// This new item may have changed the maximum dQ of [x], so we must update it.
			newMax = dq[current->x].v->returnMaxStored();	// (step 3)
			if (ioparm.textFlag>1) { cout << "  (3) dq["<<current->x<<"]'s old maximum was (" << dq[current->x].heap_ptr->m <<" "<< dq[current->x].heap_ptr->j<< ")\t"<<dq[current->x].heap_ptr<<endl; }
			h->updateItem(dq[current->x].heap_ptr, newMax);
			if (ioparm.textFlag>1) {
				cout << "      dq["<<current->x<<"]'s new maximum  is (" << dq[current->x].heap_ptr->m <<" "<< dq[current->x].heap_ptr->j<< ")\t"<<dq[current->x].heap_ptr<<endl;
				cout << "  (4) updating dq["<<j<<"] to ("<<current->x<<" "<<current->y+axai<<")"<<endl;
			}

			// And we must add an element (x,+) to [j], since [j] as acquired a new connection
			// to [x] (via absorbing [i]).
			dq[j].v->insertItem(current->x, axai);			// (step 4)
			newMax = dq[j].v->returnMaxStored();			// (step 6)
			if (ioparm.textFlag>1) { cout << "  (6) dq["<<j<<"]'s old maximum was (" << dq[j].heap_ptr->m <<" "<< dq[j].heap_ptr->j<< ")\t"<<dq[j].heap_ptr<<endl; }
			h->updateItem(dq[j].heap_ptr, newMax);
			if (ioparm.textFlag>1) { cout << "      dq["<<j<<"]'s new maximum  is (" << dq[j].heap_ptr->m <<" "<< dq[j].heap_ptr->j<< ")\t"<<dq[j].heap_ptr<<endl; }

		}    //  (current->x != i && !dq[i].v->findItem(current->x))
		
		temp    = current;
		current = current->next;						// move to next element
		delete temp;
		temp = NULL;
		t++;
	}    // while (current!=NULL)
	
	// Now that we've updated the connections values for all of [i]'s and [j]'s neighbors, 
	// we need to update the a[] vector to reflect the change in fractions of edges after
	// the join operation.
	if (ioparm.textFlag>1) {
		cout << endl;
		cout << "  whoops. no more elements for community "<< j << endl;
		cout << "  (7) updating a["<<j<<"] = " << a[i] + a[j] << " and zeroing out a["<<i<<"]" << endl;
	}
	a[j] += a[i];								// (step 7)
	a[i] = 0.0;
	
	// ---------------------------------------------------------------------------------
	// Finally, now we need to clean up by deleting the vector [i] since we'll never
	// need it again, and it'll conserve memory. For safety, we also set the pointers
	// to be NULL to prevent inadvertent access to the deleted data later on.

	if (ioparm.textFlag>1) { cout << "--> finished merging community "<<i<<" into community "<<j<<" and housekeeping.\n\n"; }
	delete dq[i].v;							// (step 8)
	dq[i].v        = NULL;						// (step 8)
	dq[i].heap_ptr = NULL;						//
	
	return;
 
}

// ------------------------------------------------------------------------------------

bool parseCommandLine(int argc,char * argv[]) {
	int argct = 1;
	string temp, ext;
	string::size_type pos;
	char **endptr;
	long along;
	int count;

	// 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>		period of timer for reporting progress of computation to screen
	// -s			calculate and track the support of the dQ matrix
	// -v --v ---v		differing levels of screen output verbosity
	// -c <int>		record the aglomerated network at step <int>
	
	if (argc <= 1) { // if no arguments, return statement about program usage.