Base model
/*
* 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;}
}
