Network.java
From Santa Fe Institute Events Wiki
/*
* Network.java * * Created on January 18, 2005, 4:09 PM * Modified June 14, 2006 * * This class generates a network, runs some * net statistics, and writes it to a pajek-formatted file */
package CoopNetBlue; //import java.util.Random; import uchicago.src.sim.network.NetworkFactory; import uchicago.src.sim.network.EdgeFactory; import java.util.Formatter; import uchicago.src.sim.util.Random; import java.util.ArrayList; import uchicago.src.sim.gui.OvalNetworkItem; import rlriolo.ioutils.*; import java.io.PrintWriter; import java.util.HashSet; import uchicago.src.sim.util.*; import java.util.Vector;
/**
* * @author Jack Waddell */
public class Network {
//******************************************************* // static parameters
// the main model public static CoopNetBlue model;
//*******************************************************
// Instance parameters
public int[][] adjacencyMatrix; // Yes, it is Aij = 1 if j -> i.
public int networkSize; // The number of agents
public int connectRadius; // The radius for grid or SWN inits
public double reconnectProb; // The prob or (re)wiring in (SWN) or random net
// a pointer to the agent list,
public ArrayList<CustomNode> agentList = new ArrayList<CustomNode>();
// These are for writing a pajek-formatted file
protected String pajekFileName = "pajek";
protected String outputDirName = "./";
protected PrintWriter pajekFile, plaintextPajekFile;
////////////////////////////////////////////////////////////////////////
// Constructor
public Network(int networkSize, int connectRadius, double reconnectProb){
this.networkSize = networkSize; this.connectRadius = connectRadius; this.reconnectProb = reconnectProb;
}
///////////////////////////////////////////////////////////////////////
// buildAdjacencyMatrix
// Inputs: int netType, selects which specific type of matrix to form
// Outputs: int[][], the adjacency matrix
public int[][] buildAdjacencyMatrix(int netType){
switch(netType){ case 0 : return buildAdjacencyMatrix2DWS(); case 1 : return buildAdjacencyMatrixWS(); case 2 : return buildAdjacencyMatrixRand(); default: return buildAdjacencyMatrix2DWS(); }
}
///////////////////////////////////////////////////////////////////////////
//
// buildAdjacencyMatrixWS
// Develops an adjacency matrix for a Watts-Strogatz Small World
// network based on the given parameters. Note that this
// implementation uses a disconnecting rewire, so that it is
// possible to disconnect groups in the network. It is also
// possible to have less than an average degree of 2x connectRadius,
// since a connection can be "overwritten" during the rewire.
//
// Inputs: double reconnectProb: each neighbor connection
// has a probability p of being disconnected from the outgoing side (i)
// and reattached to a random node (including the one from which it
// was just disconnected, and any other nodes that j goes to.)]
// connectRadius: the number of neighbors to either side of each node.
// Note that this often leads to cycles.
public int[][] buildAdjacencyMatrixWS(){
adjacencyMatrix = new int[networkSize][networkSize];
// Make the regular gride
for(int i = 0; i < networkSize; i++){
for(int j = i; j< networkSize; j++){
if( (j <= (i + connectRadius) ) && (i!=j) ){
adjacencyMatrix[i][j] = 1;
adjacencyMatrix[j][i] = 1;
}
else if( (j >= (networkSize - connectRadius + i) ) && (i!=j)){
adjacencyMatrix[i][j] = 1;
adjacencyMatrix[j][i] = 1;
}
else{
adjacencyMatrix[i][j] = 0;
adjacencyMatrix[j][i] = 0;
}
}
}
// Do random rewiring double randomDouble;
for(int i = 0; i < networkSize; i++){
for(int j = 1; j < networkSize; j++){
randomDouble = model.getUniformDoubleFromTo(0,1);
if((randomDouble < reconnectProb)&&
(adjacencyMatrix[i][j]==1)){ adjacencyMatrix[i][j] = 0; int randomi = j; do{ randomi = model.getUniformIntFromTo(0, networkSize - 1); if(model.rDebug > 2) System.out.printf("j = %d, randomi = %d, A[i][j] = %d\n", j,randomi, adjacencyMatrix[randomi][j]); } while (randomi == j || adjacencyMatrix[randomi][j] ==1);
adjacencyMatrix[randomi][j] = 1; adjacencyMatrix[j][randomi] = 1;
}
}
}
return adjacencyMatrix; }
///////////////////////////////////////////////////////////////////////////
//
// buildAdjacencyMatrix2DWS
// Develops an adjacency matrix for a Toroidal - Watts-Strogatz Small
// World network based on the given parameters. Note that this
// implementation uses a disconnecting rewire, so that it is
// possible to disconnect groups in the network.
public int[][] buildAdjacencyMatrix2DWS(){
// Make regular grid
adjacencyMatrix = new int[networkSize][networkSize];
int ix, iy, jx, jy;
int size = (int) Math.floor(Math.sqrt(networkSize));
System.out.printf("Size = %d \n", size);
for(int i = 0; i < networkSize; i++){
for(int j = i; j< networkSize; j++){
ix = i % size;
iy = i / size;
jx = j % size;
jy = j / size;
double dx = Math.min( Math.min( Math.pow(jx - ix,2),
Math.pow(jx + size - ix, 2)), Math.pow(jx - size - ix, 2) );
double dy = Math.min( Math.min( Math.pow(jy - iy,2),
Math.pow(jy + size - iy, 2)), Math.pow(jy - size - iy, 2) );
if( (Math.sqrt(dx + dy) <= (connectRadius) ) && (i!=j) ){
adjacencyMatrix[i][j] = 1;
adjacencyMatrix[j][i] = 1;
}
else{
adjacencyMatrix[i][j] = 0;
adjacencyMatrix[j][i] = 0;
}
}
}
double randomDouble;
// Do random rewiring
for(int i = 0; i < networkSize; i++){
for(int j = 1; j < networkSize; j++){
randomDouble = model.getUniformDoubleFromTo(0,1);
if((randomDouble < reconnectProb)&&
(adjacencyMatrix[i][j]==1)){ adjacencyMatrix[i][j] = 0; int randomi = j; do{ randomi = model.getUniformIntFromTo(0, networkSize - 1); System.out.printf("j = %d, randomi = %d, A[i][j] = %d\n", j,randomi, adjacencyMatrix[randomi][j]); } while (randomi == j || adjacencyMatrix[randomi][j] ==1);
adjacencyMatrix[randomi][j] = 1; adjacencyMatrix[j][randomi] = 1;
}
}
}
System.out.printf("----> Finished 2DWS Adjacency Mat\n");
return adjacencyMatrix;
}
///////////////////////////////////////////////////////////////////////////
//
// buildAdjacencyMatrixStar
// Develops an adjacency matrix for a Star Network, centered on i.
public int[][] buildAdjacencyMatrixStar(int i){
adjacencyMatrix = new int[networkSize][networkSize];
int ix, iy, jx, jy;
for(int k = 0; k < networkSize; k++){
for(int j = 0; j< networkSize; j++){ adjacencyMatrix[k][j] = 0; adjacencyMatrix[j][k] = 0; } }
for(int j = 0; j< networkSize; j++){ if(i!=j){ adjacencyMatrix[i][j] = 1; adjacencyMatrix[j][i] = 1; } }
System.out.printf("----> Finished Star Adjacency Mat\n");
return adjacencyMatrix;
}
//////////////////////////////////////////////////////////////////
// buildAdjacencyMatrixRand
// Develops a symmetric, random adjacency matrix, so that the
// probability of an edge existing between any pair of nodes is
// reconnectProb.
public int[][] buildAdjacencyMatrixRand(){
adjacencyMatrix = new int[networkSize][networkSize];
int i, j;
double randn;
for(i = 0; i < networkSize; i++){
for(j = 0; j < networkSize; j++){ randn = model.getUniformDoubleFromTo(0, 1);
if (randn < reconnectProb){ adjacencyMatrix[i][j] = 1; adjacencyMatrix[j][i] = 1; } //else // System.out.printf("Randn = %f vs %f\n", randn, reconnectProb); } }
System.out.printf("----> Finished Random Adjacency Mat\n");
return adjacencyMatrix; }
///////////////////////////////////////////////////////////////////////
// buildAgentList
// Develops an arrayList of CustomNodes interconnected based on the
// adjacency matrix developed.
public void buildAgentList(){
// Create all the agents
for(int i = 0; i < networkSize; i++){
OvalNetworkItem drawable = new OvalNetworkItem(0,0);
double strategy = model.getUniformDoubleFromTo(0, 1);
CustomNode agent = new CustomNode(drawable, strategy);
agentList.add(agent);
}
// Create the edges between them, governed by the adjacency // matrix
CustomEdge edge;
double cc;
CustomNode jnode, inode;
for(int i = 0; i < networkSize; i++){
for(int j = 0; j < networkSize; j++){
if(adjacencyMatrix[i][j] == 1){
jnode = (CustomNode) agentList.get(j);
inode = (CustomNode) agentList.get(i);
edge = new CustomEdge(jnode, inode);
jnode.addOutEdge(edge);
inode.addInEdge(edge);
// This symmetritizes the network // i.e. makes undirected edge = new CustomEdge(inode, jnode); inode.addOutEdge(edge); jnode.addInEdge(edge);
}
}
}
}
/////////////////////////////////////////////////////////////
// printAdjacencyMatrix
// a debugging tool. Prints the adjacency matrix to the terminal
public void printAdjacencyMatrix(){
System.out.printf("--- Printing Adjacency Matrix, size %d ---\n",
networkSize);
for(int i = 0; i < networkSize; i++){
for(int j = 0; j < networkSize; j++){
System.out.printf(" %d ", adjacencyMatrix[i][j]);
}
System.out.printf("\n");
}
}
//////////////////////////////////////////////////////////////
// writePajekNetwork
// Writes the network to a file in pajek
// format. Note: this version writes DOS type line feeds.
public void writePajekNetwork(ArrayList<CustomNode> agentList){
String verts, arcs; // These are carriage return and line feed in DOS format. char cr = (char) 13; char lf = (char) 10;
// pajek requires the vertices and arcs separately. verts = String.format("*Vertices %d%c%c", networkSize, cr, lf); arcs = String.format("*Arcs %c%c", cr, lf);
// step through all nodes for(int i = 0; i < networkSize; i++){ CustomNode inode = (CustomNode) agentList.get(i); verts += String.format("%d \"N%d: %d\"", inode.getID() + 1, inode.getID(), inode.getUtility());
verts += String.format(" ic %s%c%c", inode.getMyPajekColor(),cr, lf);
ArrayList edgesInList = inode.getInEdges(); int numEdges = edgesInList.size(); CustomNode testNode = (CustomNode) (model.agentList).get(i); if (testNode != inode) System.out.printf("Nodes(%d) not equal\n", i); if ( (testNode.getOutDegree() != inode.getOutDegree()) || (testNode.getInDegree() != inode.getInDegree())) System.out.printf("Nodes(%d) have different degree\n", i); if (numEdges > 0) // if node has at least one neighbor, write the edges for(int j = 0; j < numEdges; j++){ CustomEdge edge = (CustomEdge)edgesInList.get(j); arcs += String.format("%d %d %c%c", ((CustomNode)edge.getFrom()).getID() + 1, ((CustomNode)edge.getTo()).getID() + 1, cr, lf); } } String s = verts + arcs; writeToPajekFile(s);
}
/////////////////////////////////////////////////////////////
// writeLineToPajekFile
// writes a single line to the pajek file
public void writeLineToPajekFile ( String line ) {
if ( pajekFile == null ) { return; } else { pajekFile.println( line ); }
}
//////////////////////////////////////////////////////////
// writeToPajekFile
// Does the same.
public void writeToPajekFile ( String line ) {
if ( pajekFile == null ) { return; } else { pajekFile.print( line ); }
}
//////////////////////////////////////////////////////////////
// startPajekFile
// opens a file to write the pajek network to.
public PrintWriter startPajekFile () {
if ( model.rDebug > 0 ) System.out.println( "startPajekFile called!" ); pajekFile = null; String fullFileName = pajekFileName + String.format( "%02d.net", model.runNumber );
pajekFile = IOUtils.openFileToWrite( outputDirName, fullFileName, "r" ); if ( model.rDebug > 0 ) System.out.println( "startPajekFile completed!" );
return pajekFile;
}
//////////////////////////////////////////////////////////////
// startPajekFile - overload
// opens a file to write the pajek network to. Calls it
// by integer i
public PrintWriter startPajekFile (int i) {
if ( model.rDebug > 0 ) System.out.println( "startPajekFile called!" ); pajekFile = null; String fullFileName = pajekFileName + String.format( "%03d.%02d.net", i, model.runNumber );
pajekFile = IOUtils.openFileToWrite( outputDirName, fullFileName, "r" );
if ( model.rDebug > 0 ) System.out.println( "startPajekFile completed!" ); return pajekFile;
}
//////////////////////////////////////////////////////////
// endPajekFile
// closes the open pajekFile
public void endPajekFile ( ) {
IOUtils.closePWFile( pajekFile );
}
///////////////////////////////////////////////////////////
// getAverageCC1
// Calculates the average 1-neighborhood clustering coefficient
public double getAverageCC1(){
CustomNode node = null; double sum = 0; for(int i = 0; i < agentList.size(); i ++){ node = (CustomNode) agentList.get(i); sum += getNodeCC1(node); } return sum / (double) agentList.size();
}
//////////////////////////////////////////////////////////
// getAverageCC2
// Calculates the average 2-neighborhood clustering coefficient
public double getAverageCC2(){
CustomNode node = null; double sum = 0; for(int i = 0; i < agentList.size(); i ++){ node = (CustomNode) agentList.get(i); sum += getNodeCC2(node); } return sum / (double) agentList.size();
}
///////////////////////////////////////////////////////// // union // Support function. // Returns the union of two array lists of nodes public ArrayList<CustomNode> union(ArrayList<CustomNode> l1,
ArrayList<CustomNode> l2){ ArrayList<CustomNode> unionList = new ArrayList<CustomNode>(); unionList.addAll(l1); for(int i = 0; i < l2.size(); i ++){ CustomNode node = (CustomNode) l2.get(i); if (!unionList.contains(node)) unionList.add(node); } return unionList;
}
///////////////////////////////////////////////////////////// // intersection // Support function // Return the intersection of two array lists of nodes public ArrayList<CustomNode> intersection(ArrayList<CustomNode> l1,
ArrayList<CustomNode> l2){ ArrayList<CustomNode> interList = new ArrayList<CustomNode>(); for(int i = 0; i < l1.size(); i ++){ CustomNode node = (CustomNode) l1.get(i); if (l2.indexOf(node) >-1) interList.add(node); } return interList;
}
/////////////////////////////////////////////////////////////
// getNodeCC1
// Computes the clustering coefficient CC1, as per Pajek documentation
// This is the 1-neighborhood clustering coefficient
public double getNodeCC1 (CustomNode node){
ArrayList<CustomNode> neighborsList = new ArrayList<CustomNode>(); // Get all neighbors neighborsList = union(node.getOutNodes(), node.getInNodes()); int sum = 0; int k = neighborsList.size(); for(int j = 0; j < k; j ++){ CustomNode jnode = (CustomNode) neighborsList.get(j); ArrayList<CustomNode> nOut = jnode.getOutNodes(); ArrayList<CustomNode> nIn = jnode.getInNodes();
sum += (intersection(nOut, neighborsList)).size(); sum += (intersection(nIn, neighborsList)).size();
} double cc1 = 0; if (k > 1) cc1 = (double)sum/( 2* (double)k * (double)(k-1)); return cc1;
}
/////////////////////////////////////////////////////////////
// getNodeCC2
// computes the clustering coefficient CC2, as per Pajek documentation
// E(G1(v))/E(G2(v))
// This is the 2-neighboorhood clustering coefficient
public double getNodeCC2 (CustomNode node){
// calc E(G1(v)) = sum1 ArrayList<CustomNode> neighbors1List = new ArrayList<CustomNode>(); ArrayList<CustomNode> neighbors2List = new ArrayList<CustomNode>(); neighbors1List = union(node.getOutNodes(), node.getInNodes()); neighbors2List.addAll(neighbors1List);
int sum1 = 0; int k = neighbors1List.size(); for(int j = 0; j < k; j ++){ CustomNode jnode = (CustomNode) neighbors1List.get(j); ArrayList<CustomNode> nOut = jnode.getOutNodes(); ArrayList<CustomNode> nIn = jnode.getInNodes();
sum1 += (intersection(nOut, neighbors1List)).size(); //sum1 += (intersection(nIn, neighbors1List)).size();
neighbors2List = union(neighbors2List, union(nOut, nIn)); }
//System.out.printf("For node %d sum1 = %d\n", node.getID(), sum1);
int index = neighbors2List.indexOf(node);
while (index > 0){
//System.out.printf("node index = %d\n", index);
neighbors2List.remove(index);
index = neighbors2List.indexOf(node);
}
// calc E(G2(v)) = sum2 int sum2 = 0; int ind1, ind2; for(int j = 0; j < neighbors2List.size(); j++){
CustomNode jnode = (CustomNode) neighbors2List.get(j); ArrayList<CustomNode> nOut = jnode.getOutNodes(); ArrayList<CustomNode> nIn = jnode.getInNodes();
sum2 += (intersection(nOut, neighbors2List)).size(); //sum2 += (intersection(nIn, neighbors2List)).size();
ind1 = neighbors2List.indexOf(jnode); ind2 = neighbors2List.lastIndexOf(jnode); if (ind1 != ind2) System.out.printf ("Node %d in list multiple times\n", jnode.getID());
}
//System.out.printf("For node %d sum1 = %d\n", node.getID(), sum2);
double cc2 = 0;
if (sum2 > 0)
cc2 = (double)sum1/(double)sum2;
return cc2;
}
/////////////////////////////////////////////////////////
// printList
// Debug tool
// Prints the contents of an ArrayList
public void printList(ArrayList<CustomNode> list){
for(int i = 0; i < list.size(); i++){ CustomNode node = (CustomNode) list.get(i); System.out.printf("%d, ", node.getID());
} System.out.printf("\n");
}
///////////////////////////////////////////////////////////
// PickRandomEdge
// Picks a random edge with uniform probability in O(m/(n*n))
// (I think)
public CustomEdge pickRandomEdge(){
CustomEdge edge = null; CustomNode inode; CustomNode jnode; do{ inode = agentList.get(model.getUniformIntFromTo(0, agentList.size() -1)); do{ jnode = agentList.get(model.getUniformIntFromTo(0, agentList.size() -1)); } while (inode == jnode);
if ( (jnode.getOutNodes()).contains(inode)) edge = getEdgeFromTo(jnode, inode); } while (edge == null); return edge;
}
///////////////////////////////////////////////////////////
// selectRandomUncoupledPair
// Selectrs a random pair of nodes with uniform probability.
public CustomNode[] selectRandomUncoupledPair(){
boolean pass = false; CustomNode inode, jnode; int i, j; CustomEdge edge; do{ i = model.getUniformIntFromTo(0, agentList.size() -1); do{ j = model.getUniformIntFromTo(0, agentList.size() -1); } while (i == j);
inode = (CustomNode) agentList.get(i); jnode = (CustomNode) agentList.get(j); if ( !(jnode.getOutNodes()).contains(inode)){ pass = true; } } while (!pass); CustomNode[] nodes = {inode, jnode}; return nodes;
}
////////////////////////////////////////////////////////////
// selectRandomUncoupledNode
//
public CustomNode selectRandomUncoupledNode(CustomNode jnode){
boolean pass = false; CustomNode inode = null; int i, j = jnode.getID(); CustomEdge edge; // get a list of the nodes, but make sure it isn't the main list // 'cause we're gonna shuffle it ArrayList <CustomNode> nodesList = new ArrayList<CustomNode>(); nodesList.addAll(agentList); SimUtilities.shuffle(nodesList, Random.uniform);
i = 0; int k = 0; do{
inode = (CustomNode) nodesList.get(i); if (inode != jnode){ if ( !(jnode.getOutNodes()).contains(inode)){ pass = true; } } i++; if (i == nodesList.size()){ i = 0; k ++; } } while ( !pass && k < 2 );
if (k == 2){ do{ i = model.getUniformIntFromTo(0, agentList.size() - 1); inode = (CustomNode) agentList.get(i); } while ( i == j || (jnode.getOutNodes()).contains(inode)); } return inode;
}
// getters and setters
public String getPajekFileName () { return pajekFileName; }
public void setPajekFileName ( String s ) {
pajekFileName = s;
}
public String getOutputDirName () { return outputDirName; }
public void setOutputDirName ( String s ) {
outputDirName = s;
}
public int getNetworkSize() {return networkSize;}
public ArrayList<CustomNode> getAgentList() {return agentList;}
public PrintWriter getPajekFile () { return pajekFile; }
public CustomEdge getEdgeFromTo(CustomNode jnode, CustomNode inode){
CustomEdge edge; HashSet edgeList = inode.getEdgesFrom(jnode); Object[] edges = edgeList.toArray(); // get the edge object connected to jnode edge = ((CustomEdge)edges[0]); return edge;
}
//**************************************************
// Static Methods
public static void setModel(CoopNetBlue m){model = m;}
}