Network Diagram

(This pattern is described in Watson, J., Hawkins, J., Bradley, D., Dassanayake, D., Wiles, J. & Hanan, J. (2005). Towards a network pattern language for complex systems. To be presented at The Second Australian Conference on Artificial Life (ACAL 2005), and published by World Scientific in the Advances in Natural Computation series. See Publications for more information.)

Submitted by: James Watson, John Hawkins, Daniel Bradley, Dharma Dassanayake, Jim Hanan, Scott Heckbert, and Andrew Hockey.

1a. Pattern name: Network Diagram

1b. Classification: Visualization (Structure, Dynamics, Function, Micro, Macro, State Space)

2. Intent. A fundamental property of complex systems is that the interactions between micro-level components result in emergent macro level behaviour. This emergent behaviour means that it is difficult to know which components are of interest. In addition, there are large numbers of possible metrics available to analyze the properties of a complex system. Thus, a common starting point is to simply generate some form of initial visualization of components and their interactions.

A network diagram provides a spatial representation of entities and their relationships. By hiding the specifics of entities and their relationships, an initial overview of the complex system is provided. For example, a tabular description of genes and their interactions makes it difficult to follow the paths of gene activation. By depicting each gene as a node and its interactions as links between nodes, we gain an immediate impression of paths of activation. This is achieved by removing superfluous information such as gene name, etc., and by providing an intuitive spatial representation.

Furthermore, numerous views of the same system can be generated by changing what the nodes and links represent. This flexibility allows researchers to home in on the pertinent features of the system.

3. Also known as: Graph

4. Motivation. Static System: Characterizing the nature of co-author relationships in a given academic field is difficult when browsing a textual description of their collaborations. Visualizing authors as nodes and co-authorship as links renders large amounts of information visually accessible.

Dynamic System: When investigating state spaces, an activation diagram makes it difficult to determine properties such as cyclic behaviour, length of cycles, etc. By removing information such as individual entity states for each time step, and visualizing unique states as nodes and the transitions between them as links, such properties are immediately apparent.

5. Applicability. The Network Diagram pattern can be applied whenever you can define entities and their relationships. In many physical systems, there is a an obvious way to define the system as entities and relationships. For example, regulations between genes, interactions between people, etc. However, the Network Diagram has wider applicability than these corporal mappings. More abstract properties of a system, such as state space transitions, can also benefit from the Network Diagram visualization.

6. Structure. (Intentionally left blank).

7. Participants. Node, Links, Layout, Manipulation

8. Collaborations. Entities are represented as nodes, with their relationships represented as links between these nodes. The nodes are placed in a spatial representation defined by the layout. Manipulation provides a means of interacting with all aspects of the Network Diagram (such as layout, node states, etc.).

9. Consequences. The Network Diagram focuses on the entities and relationships of interest.

it focuses on the relationships of interest
layout allows different views, possibly different interpretations
ease of view / analysis comes from reduction of information
generality means one has to choose entities / relationships
- this is a strength and a weakness
  - strength: flexibility
  - weakness: lack of guidance of what should be nodes and links

10. Implementation.

there are lots of different layouts / methods of manipulation, which can largely influence usefulness
giving user choice over layout (and manipulation) is a useful approach
a random layout is the simplest to implement, but is generally unsuitable for (e.g.) visualizing the giant component of the network. Increasingly sophisticated network layout algorithms can incur a cost in processor time (many optimal layouts are likely to be NP-complete).

11. Sample code.

n = network, indexed by node
p = position of each node

clear the screen
for i = 1 to (number of nodes in n):
    p[i] = random position
    draw sphere at p[i]

for i = 1 to (number of nodes in n):
    r = list of nodes regulated by n[i]
    for j = 1 to (number of nodes in r):
        draw arrow from p[i] to p[r[j]]

(Further sample code is included at the end of this document.)

12. Known uses. Boolean network visualization and design, social network visualization, neural network visualization and design.

13. Related patterns. Discrete State-Space Trajectory Diagram, Activation Diagram.

Appendix A - Further Sample Code

What follows is an implementation of the Network Diagram in three dimensions using C++, OpenGL and wxWidgets.

Initialization of window and drawing canvas, and declaration of window event table and destructor:

NBrowser::NBrowser(GenomeDisplay *parent)
: wxFrame(parent, -1, "", wxDefaultPosition, wxSize(630,450))
{
      gDisplay = parent;
      num = gDisplay->num;

      wxString title = "Gene Network of Genome " +
                  wxString::Format("%d", num);
      SetTitle(title);

      wxMenu *menu = new wxMenu;
      menu->Append(NB_SAVE_TEXT, "&Text");
      menu->Append(NB_SAVE_PAJEK, "&Pajek");

      wxMenuBar *menubar = new wxMenuBar;
      menubar->Append(menu, "&Export");
      SetMenuBar(menubar);

      canvas = new NCanvas(this);
}

NBrowser::~NBrowser()
{
      delete canvas;
}

BEGIN_EVENT_TABLE(NBrowser, wxFrame)
      EVT_MENU(NB_SAVE_TEXT, NBrowser::textExport)
      EVT_MENU(NB_SAVE_PAJEK, NBrowser::pajekExport)
      EVT_CLOSE(NBrowser::OnClose)
END_EVENT_TABLE()

void NBrowser::OnClose(wxCommandEvent & event)
{
      Show(false);
}

void NBrowser::update()
{
      canvas->update();
}

NCanvas::NCanvas(NBrowser *parent)
            : wxGLCanvas(parent, -1, wxDefaultPosition, wxDefaultSize)
{
      gDisplay = parent->gDisplay;
      x = -1000;
      y = -1000;

      SetCurrent();
      glMatrixMode(GL_PROJECTION);

      update();
}

NCanvas::~NCanvas()
{
}

BEGIN_EVENT_TABLE(NCanvas, wxGLCanvas)
      EVT_SIZE(NCanvas::OnSize)
      EVT_PAINT(NCanvas::OnPaint)
      EVT_ERASE_BACKGROUND(NCanvas::OnEraseBackground)
      EVT_MOTION(NCanvas::OnMouseMotion)
END_EVENT_TABLE()

Event handlers that deal with window events:

void NCanvas::OnSize(wxSizeEvent & event)
{
      int width, height;
      GetClientSize(&width, &height);
      if (GetContext())
      {
            SetCurrent();
            glViewport(0, 0, width, height);
      }
}

void NCanvas::OnEraseBackground(wxEraseEvent & event)
{
      // to avoid flashing
}

void NCanvas::OnPaint(wxPaintEvent & event)
{
      wxPaintDC dc(this);
      renderNetwork();
}

Allow mouse movements to control the 3D angle of visualization:

void NCanvas::OnMouseMotion(wxMouseEvent & event)
{
      /* coordinates returned by event are such that the top
      * left-hand corner is (0,0) and bottom-right is size */
      int width, height;
      GetClientSize(&width, &height);
      int x_win = event.GetX();
      int y_win = event.GetY();

      double x_fraction = (double)x_win / (double)width;
      double y_fraction = (double)y_win / (double)height;
      double this_x = -1 + x_fraction * 2;
      double this_y = 1 - y_fraction * 2;

      double xDist = 0.0;
      double yDist = 0.0;
      if (x == -1000)         // initialize the first time
      {
            x = this_x;
            y = this_y;
      }
      if (x != this_x)
            xDist = this_x - x;
      if (y != this_y)
            yDist = this_y - y;
      x = this_x;
      y = this_y;

      if (event.LeftIsDown())
      {
            if (xDist > 0)                // rotate right
                  glRotatef(-2.0, 0.0, 1.0, 0.0);
            else if (xDist < 0)           // rotate left
                  glRotatef(2.0, 0.0, 1.0, 0.0);
            if (yDist > 0)                // rotate up
                  glRotatef(2.0, 1.0, 0.0, 0.0);
            else if (yDist < 0)           // rotate down
                  glRotatef(-2.0, 1.0, 0.0, 0.0);

            renderNetwork();
      }

      if (event.MiddleIsDown())
      {
            if (xDist > 0)                // scale larger
                  glScalef(1.04, 1.04, 1.04);
            else if (xDist < 0)           // scale smaller
                  glScalef(0.96, 0.96, 0.96);

            renderNetwork();
      }

      if (event.RightIsDown())
      {
            if (event.ShiftDown()) // move along z-axis
                  glTranslatef(0.0, 0.0, (0.04*xDist));
            else
                  glTranslatef((0.4*xDist), (0.4*yDist), 0.0);

            renderNetwork();
      }
}

Randomly choose the positions of network nodes:

void NCanvas::update()
{
      // initialize positions for gene spheres
      s_pos.resize(gDisplay->genome->gene.size());
      for (unsigned int i = 0; i < gDisplay->genome->gene.size(); i++)
      {
            s_pos[i].x = gDisplay->genome->r->getDouble(-0.95, 0.95);
            s_pos[i].y = gDisplay->genome->r->getDouble(-0.95, 0.95);
            s_pos[i].z = gDisplay->genome->r->getDouble(-0.95, 0.95);
      }

      renderNetwork();
}

Renders the network (nodes and connections) using OpenGL:

// method that renders a 3D model of gene network data
void NCanvas::renderNetwork()
{
      SetCurrent();
      glClearColor(0.0, 0.0, 0.0, 0.0);
      glClear(GL_COLOR_BUFFER_BIT | GL_DEPTH_BUFFER_BIT);
      glColor3f(0.0, 1.0, 0.0);

      // set up lighting (parameters adapted from programming guide)
      GLfloat lightPosition1[] = {1.0, 1.0, 1.0, 0.0};
      GLfloat lightPosition2[] = {0.0, 1.0, 1.0, 0.0};
      GLfloat whiteLight[] = {1.0, 1.0, 1.0, 1.0};
      GLfloat greenLight[] = {0.0, 1.0, 0.0, 1.0};
      GLfloat matSpecular[] = {1.0, 1.0, 1.0, 1.0};
      GLfloat matShininess[] = {50.0};
      //GLfloat matDiffuse[] = {0.1, 0.5, 0.8, 1.0};
      //GLfloat noMat[] = {0.0, 0.0, 0.0, 1.0};
      GLfloat lModelAmbient[] = {0.1, 0.1, 0.1, 1.0};
      //GLfloat highShininess[] = {100.0};

      glShadeModel(GL_SMOOTH);
      glMaterialfv(GL_FRONT, GL_SPECULAR, matSpecular);
      glMaterialfv(GL_FRONT, GL_SHININESS, matShininess);
      glLightfv(GL_LIGHT0, GL_POSITION, lightPosition1);
      glLightfv(GL_LIGHT0, GL_DIFFUSE, whiteLight);
      glLightfv(GL_LIGHT0, GL_SPECULAR, whiteLight);
      glLightfv(GL_LIGHT0, GL_AMBIENT, greenLight);
      glLightfv(GL_LIGHT1, GL_POSITION, lightPosition2);
      glLightfv(GL_LIGHT1, GL_DIFFUSE, greenLight);
      glLightfv(GL_LIGHT1, GL_SPECULAR, whiteLight);
      glLightfv(GL_LIGHT1, GL_AMBIENT, greenLight);
      glLightModelfv(GL_LIGHT_MODEL_AMBIENT, lModelAmbient);

      glEnable(GL_LIGHTING);
      glEnable(GL_LIGHT0);
      glEnable(GL_LIGHT1);
      glEnable(GL_DEPTH_TEST);


      // sphere specs
      float radius = 0.03;
      int slices = 20;
      int stacks = 20;

      // self-regulation disc specs
      float sreg_iradius = 0.06;
      float sreg_oradius = 0.064;
      int sreg_slices = 20;
      int sreg_rings = 1;
      float sreg_start_angle = 280; // in degrees
      float sreg_sweep_angle = 340;
      GLUquadricObj *quad = gluNewQuadric();
      gluQuadricOrientation(quad, GLU_INSIDE);
      float sreg_z_angle = 45;

      // draw the spheres
      unsigned int i;
      for (i = 0; i < s_pos.size(); i++)
      {
            glPushMatrix();
            glTranslatef(s_pos[i].x, s_pos[i].y, s_pos[i].z);
            glutSolidSphere(radius, slices, stacks);
            glPopMatrix();
      }

      // connect the spheres
      for (i = 0; i < gDisplay->genome->network.size(); i++)
      {
            vector<int> regulated = gDisplay->genome->network[i].reg;
            for (unsigned int j = 0; j < regulated.size(); j++)
            {
                  // draw an arrow from gene to regulated gene
                  gl_pos orig = s_pos[i];
                  gl_pos dest = s_pos[regulated[j]];

                  // determine if this link is inhibitory
                  bool act = false;
                  string g_val = gDisplay->genome->gene[i].value;
                  char last_char = g_val[g_val.size()-1];
                                    unsigned int result = gDisplay->genome->inhib.find(last_char);
                  if ( (result < 0) || (result >= gDisplay->genome->inhib.size()) )
                        act = true;

                  if (i == (unsigned int)regulated[j])
                  {
                        // indicate self-regulation
                        glPushMatrix();
                        glTranslatef((orig.x+sreg_iradius), orig.y, orig.z);
                        glRotatef(sreg_z_angle, 0.0, 0.0, 1.0);
                        gluPartialDisk(quad, sreg_iradius,
                              sreg_oradius, sreg_slices,
                              sreg_rings, sreg_start_angle,
                              sreg_sweep_angle);

                        // up arrow
                        gl_pos a_orig, a_dest;
                        a_orig.x=0; a_orig.y=-1.2; a_orig.z=0;
                        a_dest.x=0-sreg_iradius; a_dest.y=0.055; a_dest.z=0;
                        drawArrow(a_orig, a_dest, act);
                        glPopMatrix();
                  }
                  else // draw connecting line
                  {
                        glBegin(GL_LINES);
                        glVertex3f(orig.x, orig.y, orig.z);
                        glVertex3f(dest.x, dest.y, dest.z);
                        glEnd();
                        drawArrow(orig, dest, act);
                  }
            }
      }

      SwapBuffers();
}

Method that draws arrows:

/* method that draws an arrow given an origin and destination
* on the current matrix; the form depending on the mode of regulation */
void NCanvas::drawArrow(gl_pos orig, gl_pos dest, bool act)
{
      // get vector
      double x = dest.x - orig.x;
      double y = dest.y - orig.y;
      double z = dest.z - orig.z;

      // angle of head arm (180 degrees == PI radians)
      double t = 10.0 * PI / 180;

      // length of arrow arm
      double d = 0.08;

      // vector angle from x axis
      double g_xy = 0;
      double g_xz = 0;
      // fix angles if x <= 0
      if (x == 0)
      {
            if (y > 0)
                  g_xy = PI / 2;
            if (y < 0)
                  g_xy = -PI / 2;
            if (z > 0)
                  g_xz = PI / 2;
            if (z < 0)
                  g_xz = -PI / 2;
      }
      // y/-x -> negative angle, -y/-x -> positive angle
      else if (x < 0)
      {
            g_xy = PI + atan(y/x);
            g_xz = PI + atan(z/x);
      }
      else
      {
            g_xy = atan(y/x);
            g_xz = atan(z/x);
      }

      // point 1
      gl_pos p1;
      p1.x = dest.x + d * cos(g_xy + PI - t);
      p1.y = dest.y + d * sin(g_xy + PI - t);
      p1.z = dest.z + d * sin(g_xz + PI - t);

      // point 2
      gl_pos p2;
      p2.x = dest.x + d * cos(g_xy + PI + t);
      p2.y = dest.y + d * sin(g_xy + PI + t);
      p2.z = dest.z + d * sin(g_xz + PI + t);

      // draw arrow
      SetCurrent();
      if (act)
      {
            glBegin(GL_TRIANGLES);
            glVertex3f(dest.x, dest.y, dest.z);
            glVertex3f(p1.x, p1.y, p1.z);
            glVertex3f(p2.x, p2.y, p2.z);
            glEnd();
      }
      else
      {
            glBegin(GL_LINE_LOOP);
            glVertex3f(dest.x, dest.y, dest.z);
            glVertex3f(p1.x, p1.y, p1.z);
            glVertex3f(p2.x, p2.y, p2.z);
            glEnd();
      }
}

About this document ...

Towards a Network Pattern Language for Complex Systems

This document was generated using the LaTeX2HTML translator Version 2002-2-1 (1.70)

The command line arguments were:
latex2html -split 0 -no_navigation acal-2005_preprint.tex