Feb 27: Network visualization

Graphs
Force-directed layout
Some networks
Practice problems

Graphs

Most everything we've done has treated things as being independent of each other (can you remember one big exception?). But there are many cases where we want to process relationships among things -- social networks (who is friends with whom), biological networks (how are signals carried through the cell), and, yes, even computer networks (how do web pages point to each other). There is a lot of work out there on analyzing such networks; e.g., see the Visual Complexity site for some nice examples.

Just as floats and ints represent numbers and Strings represent text, graphs represent pairwise relationships among things. Processing doesn't have a Graph class built in, so we'll build our own very simple one here. A graph consists of two types of things: vertices (sometimes called nodes) represent the individual objects (e.g., people, proteins, or web pages), and edges represent their relationships (e.g., is friends with, passes a signal to, or links to). Sometimes there's a directionality (e.g., links to vs. is linked from), but we won't worry about that here. When we depict a graph, we typically draw vertices as circles and edges as lines connecting them (see the above-mentioned Visual Complexity site). In the following example, Alice and Bob are friends, as are Alice and Diane; everybody's friends with Kevin and nobody's friends with poor old Ebenezer.

To load a graph into a program, we need to say what the vertices represent, and which vertices have edges between them. There are numerous possible file formats; the following sketch uses the core of the Pajek format. In this format, we first have a line that says the number of vertices. We then have one line per vertex, giving it an id number and a label (e.g., the person's name). If a label has spaces, it should be in double quotes. Next is a line that says edges are coming next (although we don't say how many), followed by one line per edge, giving the id numbers of the related vertices. For example:

*Vertices 8
1 Alice
2 Bob
3 Charlie
4 Diane
5 Ebenezer
6 Francine
7 Ida
8 Kevin
*Edges
1 2
1 4
1 7
1 8
2 8
3 8
4 7
4 8
6 7
6 8
7 8

The following sketch reads in a file following this format, and fills in a Graph object with Vertex and Edge objects. The details of the reader are a bit hairy (using the text processing functions); don't worry about them unless you're interested in coming up with your own reader. What's more important is the structure of the objects that have been read in.

sketch1

void setup()
{
  Graph g = new Graph();
  readPajek(g,"friends.txt");
  g.print();
}

Graph

class Vertex {
  String label;
  
  Vertex(String label)
  {
    this.label = label;
  }
}

class Edge {
  Vertex a, b;
  
  Edge(Vertex a, Vertex b)
  {
    this.a = a; this.b = b;
  }
}

class Graph {
  Vertex[] vertices;
  Edge[] edges;
 
  // Display the labels of the vertices and of the vertices for the edges 
  void print()
  {
    println("Vertices"); println("--------");
    for (int i=0; i<vertices.length; i++)
      println(vertices[i].label);

    println(); println("Edges"); println("-----");
    for (int i=0; i<edges.length; i++)
      println(edges[i].a.label+","+edges[i].b.label);
  }
}

[sketch1.pde][Graph.pde][pajek.pde][friends.txt]

Force-directed layout

Given a bunch of vertices and edges, how can we nicely lay out the graph, as in the friends example above? If we just put the vertices at random positions, they aren't likely to be near their neighbors, and we'll have lines for edges going all over the place. This brings us back to the approach that we saw before that modeled relationships -- springs. Basically, we want to put a spring for each edge, so that neighbors try to be close together. That's not quite enough though, because multiple neighbors of a single vertex (that weren't themselves connected) could try to be in the same place. There's nothing to keep Alice's friends Diane and Bob from overlapping. In addition to springs, we need repulsion (insert your own joke here about repulsion in social networks).

Let's go back to pseudo-physics and come up with a model of repulsion. We dealt before with gravity between a small object and a massive one, which just made the small object accelerate towards the massive one (downward). The underlying gravitational model has each object pull the other towards it (remember that you are indeed pulling the earth towards you just a bit). We'll take that model and just make the objects push away from each other (like aligned magnets, or the same electrical charge). The standard model is F = G*m_i*m_j / d_ij², where G is the gravitational constant, m_i and m_j are the masses of the objects, and d_ij is the distance between the objects.

The following sketch uses the Ball class from the pseudophysics lecture (each has a position and velocity, and bounces off the walls), and applies repulsion (a negative G) between each pair. Note the nested for-loop to handle each pair just once (1,2 but not 2,1), by starting j at i+1. We ignore masses, so the formula is simplified. We also separate out the component of the force that's applied in the x direction and in the y direction. Some user interface stuff allows a ball to be dragged around (foregoing any other forces).

int num = 10;
Ball[] balls = new Ball[num];

int G = 50;  // strength of repulsion

int dragging = -1;  // which ball is being dragged (-1 if none)

void setup()
{
  size(400,300);
  smooth();
  noStroke();

  // Start them at random places
  for (int i=0; i<num; i++)
    balls[i] = new Ball(random(width),random(height)); 
}

void draw()
{
  background(0);
  
  // Draw each
  for (int i=0; i<num; i++) {
    if (i == dragging) fill(255,0,0);
    else fill(255);
    balls[i].draw();
  }
  
  // Apply repulsion for each pair
  for (int i=0; i<num; i++) {
    for (int j=i+1; j<num; j++) {
      float dij = dist(balls[i].x,balls[i].y, balls[j].x,balls[j].y);
      if (dij > 0) {
        // Compute repulsive force, and the fraction in each direction
        float f = G/(dij*dij);
        float dx = (balls[j].x-balls[i].x)/dij;
        float dy = (balls[j].y-balls[i].y)/dij;
        // Push each away from the other (unless being dragged)
        if (i != dragging) {
          balls[i].vx -= f*dx;
          balls[i].vy -= f*dy;
        }
        if (j != dragging) {
          balls[j].vx += f*dx;
          balls[j].vy += f*dy;
        }
      }
    }
  }
  // Update velocities and positions
  for (int i=0; i<num; i++) {
    if (i != dragging) balls[i].update();
  }
}

void mousePressed()
{
  // See if beginning to drag
  dragging = -1;
  for (int i=0; i<num; i++)
    if (dist(mouseX,mouseY, balls[i].x,balls[i].y) < balls[i].r)
      dragging = i;
}

void mouseDragged()
{
  // If dragging, update position
  if (dragging >= 0) {
    balls[dragging].x = mouseX;
    balls[dragging].y = mouseY;
  }
}

void mouseReleased()
{
  // Stop dragging and put it at rest (0 velocity)
  if (dragging >= 0) {
    balls[dragging].vx = 0;
    balls[dragging].vy = 0;
    dragging = -1;
  }
}

void keyPressed()
{
  if (key=='G') {  // more repulsion
    G+=10;
    println("G:"+G);
  }
  else if (key=='g') {  // less repulsion
    if (G>10) {
      G-=10;
      println("G:"+G);
    }
  }
  else if (key=='s') {  // stop
    for (int i=0; i<num; i++) {
      balls[i].vx=0; balls[i].vy=0;
    }
  }
  else if (key=='r') {  // reset positions and velocities
    for (int i=0; i<num; i++) {
      balls[i].x = random(width); balls[i].y = random(height);
      balls[i].vx = 0; balls[i].vy = 0;
    }
  }
}

[applet]

We've now got all we need to be able to lay out a graph -- springs for edges and repulsions between all vertex pairs. In order to handle larger-scale sets of springs and repulsions, it's necessary to be a bit more careful with how forces are integrated over time. Rather than doing that ourselves, let's turn to a contributed library, Traer physics. The models are the same (though the constants somewhat different), but the results end up being better behaved.

Following is the previous repulsion sketch rewritten using the Traer physics library. (Note that the library works in 3D, so we keep using 0 for the z value, in positions and velocities.) Overall, it's at a higher level -- we just create particles and repulsions, and ask the physics module to update them. It also gives better results -- notice what happens with our set of particles.

import traer.physics.*;

int num = 10;
Particle[] ps = new Particle[num];
int r=10; // uniform radius

ParticleSystem physics;
int G = 1000;  // strength of repulsion

int dragging = -1;  // which particle is being dragged (-1 if none)

void setup()
{
  size(400,300);
  smooth();
  noStroke(); 
  
  // Create the physics module, with no inherent gravity and a small amount of drag
  physics = new ParticleSystem(0,0.1);
  
  // Create the particles, with uniform mass of 1, starting at random positions
  for (int i=0; i<num; i++)
    ps[i] = physics.makeParticle(1,random(width),random(height),0);

  // Make them repel each other
  for (int i=0; i<ps.length; i++)
    for (int j=i+1; j<ps.length; j++)
      physics.makeAttraction(ps[i], ps[j], -G, r/2);
}

void draw()
{
  background(0);

  // Draw each
  for (int i=0; i<ps.length; i++) {
    if (i==dragging) fill(255,0,0);
    else fill(255);
    ellipse(ps[i].position().x(), ps[i].position().y(), 2*r,2*r);
  }
  
  // Update    
  physics.tick();
  for (int i=0; i<ps.length; i++)
    handleBoundaryCollisions(ps[i]);
}

// Bounce off the wall (and lose a little velocity)
// From an example at the traer.physics site
void handleBoundaryCollisions(Particle p)
{
  if (p.position().x() < 0 || p.position().x() > width)
    p.setVelocity(-0.9*p.velocity().x(), p.velocity().y(), 0);
  if (p.position().y() < 0 || p.position().y() > height)
    p.setVelocity(p.velocity().x(), -0.9*p.velocity().y(), 0);
  p.moveTo(constrain(p.position().x(), 0, width), constrain(p.position().y(), 0, height), 0); 
}

void mousePressed()
{
  // See if beginning to drag
  dragging = -1;
  for (int i=0; i<num; i++) {
    if (dist(mouseX,mouseY, ps[i].position().x(),ps[i].position().y()) < r)
      dragging = i;
  }
  if (dragging >= 0) ps[dragging].makeFixed();
}

void mouseDragged()
{
  // If dragging, update position
  if (dragging >= 0)
    ps[dragging].moveTo(mouseX,mouseY,0);
}

void mouseReleased()
{
  // Stop dragging and put it at rest (0 velocity)
  if (dragging >= 0) {
    ps[dragging].makeFree();
    ps[dragging].setVelocity(0,0,0);
    dragging = -1;
  }
}

void keyPressed()
{
  if (key=='G') {  // more repulsion
    G+=100;
    println("G:"+G);
  }
  else if (key=='g') {  // less repulsion
    if (G>100) {
      G-=100;
      println("G:"+G);
    }
  }
  else if (key=='s') {  // stop
    for (int i=0; i<num; i++)
      ps[i].setVelocity(0,0,0);
  }
  else if (key=='r') {  // reset positions and velocities
    for (int i=0; i<num; i++) {
      ps[i].moveTo(random(width),random(height),0);
      ps[i].setVelocity(0,0,0);
    }
  }
}

[applet]

Some networks

Now let's put it all together. In the following sketch, Graph has a method model() that generates the springs and repulsions. Each vertex has a particle; the physics module updates the particle and thereby moves the vertex. (When the vertex wants to draw itself, it asks the particle where.)

sketch4

import traer.physics.*;

ParticleSystem physics;
int G = 1000;     // strength of repulsion
float k = 0.05;   // spring constant
float damp = 0.1; // spring damping
float rest = 50;  // spring rest length

Graph g;
PFont font;

void setup()
{
  size(400,300);
  smooth();
  noStroke(); 
  font = loadFont("David-Bold-24.vlw");
  
  physics = new ParticleSystem(0,0.1);

  g = new Graph();
  readPajek(g,"friends.txt");
  g.model(physics,G,k,damp,rest);
}

void draw()
{
  // Display
  background(255);
  g.mouseOver();
  g.draw();

  // Update  
  physics.tick();
  g.update();
}

void mousePressed()
{
  g.pressed();
}

void mouseDragged()
{
  g.dragged();
}

Graph

class Vertex {
  String label;
  Particle p;    // for the motion of this vertex
  int r=10;      // radius
  boolean isLocked=false;  // not moving
  boolean showLabel=false, showLabelOnce=false;
  
  Vertex(String label)
  {
    this.label = label;
  }

  void draw()
  {
    ellipse(p.position().x(), p.position().y(), 2*r,2*r);
  }
  
  void label()
  {
    if (isLocked || showLabel || showLabelOnce) {
      textFont(font);
      text(label, p.position().x(), p.position().y());
      showLabelOnce = false;
    }
  }

  void update()
  {
    // Bounce off the wall (and lose a little velocity)
    // From an example at the traer.physics site
    if (p.position().x() < 0 || p.position().x() > width)
      p.setVelocity(-0.9*p.velocity().x(), p.velocity().y(), 0);
    if (p.position().y() < 0 || p.position().y() > height)
      p.setVelocity(p.velocity().x(), -0.9*p.velocity().y(), 0);
    p.moveTo(constrain(p.position().x(), 0, width), constrain(p.position().y(), 0, height), 0); 
  }
}

class Edge {
  Vertex a, b;

  Edge(Vertex a, Vertex b)
  {
    this.a = a; 
    this.b = b; 
  }
  
  void draw()
  {
    line(a.p.position().x(), a.p.position().y(),
         b.p.position().x(), b.p.position().y());
  }
}

class Graph {
  Vertex[] vertices;
  Edge[] edges;
  int locked = -1;  // which vertex is being dragged (-1 if none)

  void model(ParticleSystem physics, float G, float k, float damp, float rest)
  {
    // Create the particles
    for (int i=0; i<vertices.length; i++)
      vertices[i].p = physics.makeParticle(1,random(width),random(height),0);

    // Make them repel each other
    for (int i=0; i<vertices.length; i++)
      for (int j=i+1; j<vertices.length; j++)
        physics.makeAttraction(vertices[i].p, vertices[j].p, -G, 0.25*(vertices[i].r+vertices[j].r));

    // Springs for edges
    for (int i=0; i<edges.length; i++)
      physics.makeSpring(edges[i].a.p, edges[i].b.p, k, damp, rest); 
  }  

  void draw()
  {
    // Edges first
    for (int i=0; i<edges.length; i++) {
      if (locked>=0 && (edges[i].a==vertices[locked] || edges[i].b==vertices[locked]))
        stroke(196,0,0);
      else
        stroke(128);
      edges[i].draw();
    }

    // Vertices
    noStroke();
    for (int i=0; i<vertices.length; i++) {
      if (i==locked) fill(196,0,0);
      else fill(0);
      vertices[i].draw();
    }
    
    // Labels
    for (int i=0; i<vertices.length; i++) {
      if (i==locked) fill(196,0,0);
      else fill(0,196,0);
      vertices[i].label();
    }
  }

  void update()
  {
    for (int i=0; i<vertices.length; i++)
      vertices[i].update();
  }

  void pressed()
  {  
    int grabbed = overVertex();
    if (locked >= 0 && mouseButton == LEFT) {
      // unlock existing lock
      vertices[locked].isLocked = false;
      vertices[locked].p.makeFree();
      vertices[locked].p.setVelocity(0,0,0);
      locked = -1;
    }
    
    if (grabbed >= 0) {
      if (mouseButton == LEFT) {
        // new lock
        locked = grabbed;
        vertices[locked].isLocked = true;
        vertices[locked].p.makeFixed();
      }
      else if (mouseButton == RIGHT) {
        // toggle label
        vertices[grabbed].showLabel = !vertices[grabbed].showLabel;
      }
    }
  }

  void dragged()
  {
    if (locked >= 0)
      vertices[locked].p.moveTo(mouseX,mouseY,0);
  }

  void mouseOver()
  {
    int over = overVertex();
    if (over >= 0) vertices[over].showLabelOnce = true;
  }
  
  // Returns index of vertex which the mouse is over, or -1 if none
  int overVertex()
  {
    int over=-1;
    for (int i=0; i<vertices.length; i++)
      if (dist(mouseX,mouseY, vertices[i].p.position().x(),vertices[i].p.position().y())
          < vertices[i].r)
        over = i;
    return over;
  }
}

[sketch4.pde][Graph.pde]

We can do this on larger networks, although not too large. One example of a social network is actors who have been in movies together (the Kevin Bacon game). There's a (slightly out of date now) dataset of some movies and actors, and which actors were in which movies. This dataset is too large for our system. The following sketch restricts the movies by date (say, from 2001 on) and the actors by number of roles they've had in those movies (say, at least 4). That gives us something a bit more manageable. It's still kind of hard to make sense of, but gives a feel for a more complex social network.

The basic graph code is the same, except that now edges have labels too (the movies in which the actors played). There is a special-purpose function to read in the movie data; somewhat hairy, but not the focus of what we're doing here, so treat it as a black box if you like.

[sketch5.pde][Graph.pde][movies.pde][movies.txt][actors.txt][movie_actors.txt]

Practice problems

Try with another network. You might have to adjust the various constants (spring, damping, repulsion).
Make a "browse" function, so that random individuals are highlighted at different points in time. [hints]
Choose a random index into vertices[], and set the locked variable to it. Do this every so many frames, using the modulus.
Modify the edges to have weights -- some are more closely related than others. [hints]
The weights will be the third word on each line; convert from string to int or float. Then use the weights to modulate the spring constant for the edges