ICYMI. Enjoy! -AB

***

Seeing is believing

In my field of graph theory, or network science as it is sometimes called, we study dots and lines, and the patterns formed by the dots joining up with lines. The dots are referred to as nodes and the lines are edges. Networks are combinatorial patterns, analyzed using discrete mathematics. In network science, we have the advantage over other areas of mathematics in that we can often see what we are studying in a close-up way.

Drawing networks is one part science and another art. There is well-developed area of graph theory and computer science simply called graph drawing. A good drawing of a graph can add a great deal of insight into it, and help researchers tease out its properties.

Visualizations of networks are often pretty too!

Researchers have captured the evolution of networks, like the following animation of the organizational structure in an actual company between May 2007 and June 2011. The dynamic aspects of the network reflect that employees can leave, join, or change managers in the company.

A warehouse of visualizations

If you have never visited Visual Complexity, then you should go there soon (after you read this blog, of course). The site presents a gallery of complex networks, which are real-world networks ranging from the sociological, technological, and biological. There is also network-inspired art and everything else you can imagine. Manuel Lima runs the site and he’s written two books about visualizing networked data: The Book of Trees: Visualizing Branches of Knowledge and Visual Complexity: Mapping Patterns of Information.

Here a few sample images from Visual Complexity.

Gephi

For my own students and post-docs, I direct them to the open source software Gephi. Gephi not only allows you to visualize networks, but it can extract many network statistics such as centrality measures and PageRank. While it is not for beginners and requires some background in graph theory, it is a useful and accessible tool to network science researchers.

Gephi is particularly useful for extracting community structure in networks. For this, the software uses modularity, which pulls together nodes with a higher density of edges.

Symmetry

Graphs are particularly beautiful when they possess a great deal of symmetry. A few kinds of symmetry include regularity, where every node has the same degree. There are also certain kinds of transitivity, such as vertex-transitivity where essentially all vertices satisfy the same properties (more precisely, you can automorphically map vertices to each other).

Here are some highly symmetric graphs that come with their own names. A nice garden of these is tended on Wikipedia.

Network visualizations from my research

My work in networks touches on social networks and a recent project visualizes such networks embedded in cultural works such as films or novels. This work is at the interface of graph theory, social networks, and the digital humanities. Below is a Gephi visualization of character relationships in the Twilight novel created by my graduate student David D’Angelo. The characters are nodes and two nodes are adjacent if they are spaced no more than fifteen words apart in the text. The edges are thicker if there are more of those co-occurrences; for example, Alice and Edward appear together in many scenes, as does Bella and Edward. Names were resized by their relative importance (measured by PageRank) in the text.

We also can see the breakdown (in colors) of the community structure in Twilight, with vampires, Bella’s high school friends, and characters close to Charlie.

Another recent study of mine considers a model for the evolution of social networks, called the Memoryless Geometric Protean graph model (or MGEO-P). In the model, nodes are placed randomly on a k-dimensional torus, and nodes are adjacent if they are close. “Close” here means within each other’s region of influence (governed by a random ranking function) as visualised by the blue and red squares in the figure below.

MGEO-P deepened our understanding of dimensionality in social networks, which helps explain why few attributes are needed to identify agents in the network. We call this the Logarithmic Dimension Hypothesis.

Anthony Bonato