Archive for the ‘Complex Networks’ Category

Parallel Graph Partitioning for Complex Networks

Monday, April 21st, 2014

Parallel Graph Partitioning for Complex Networks by Henning Meyerhenke, Peter Sanders, and, Christian Schulz.

Abstract:

Processing large complex networks like social networks or web graphs has recently attracted considerable interest. In order to do this in parallel, we need to partition them into pieces of about equal size. Unfortunately, previous parallel graph partitioners originally developed for more regular mesh-like networks do not work well for these networks. This paper addresses this problem by parallelizing and adapting the label propagation technique originally developed for graph clustering. By introducing size constraints, label propagation becomes applicable for both the coarsening and the refinement phase of multilevel graph partitioning. We obtain very high quality by applying a highly parallel evolutionary algorithm to the coarsened graph. The resulting system is both more scalable and achieves higher quality than state-of-the-art systems like ParMetis or PT-Scotch. For large complex networks the performance differences are very big. For example, our algorithm can partition a web graph with 3.3 billion edges in less than sixteen seconds using 512 cores of a high performance cluster while producing a high quality partition — none of the competing systems can handle this graph on our system.

Clustering in this article is defined by a node’s “neighborhood,” I am curious if defining a “neighborhood” based on multi-part (hierarchical?) identifiers might enable parallel processing of merging conditions?

While looking for resources on graph contraction, I encountered a series of lectures by Kanat Tangwongsan from: Parallel and Sequential Data Structures and Algorithms, 15-210 (Spring 2012) (link to the course schedule with numerous resources):

Lecture 17 — Graph Contraction I: Tree Contraction

Lecture 18 — Graph Contraction II: Connectivity and MSTs

Lecture 19 — Graph Contraction III: Parallel MST and MIS

Enjoy!

Adaptive-network simulation library

Wednesday, January 23rd, 2013

Adaptive-network simulation library by Gerd Zschaler.

From the webpage:

The largenet2 library is a collection of C++ classes providing a framework for the simulation of large discrete adaptive networks. It provides data structures for an in-memory representation of directed or undirected networks, in which every node and link can have an integer-valued state.

Efficient access to (random) nodes and links as well as (random) nodes and links with a given state value is provided. A limited number of graph-theoretical measures is implemented, such as the (state-resolved) in- and out-degree distributions and the degree correlations (same-node and nearest-neighbor).

Read the tutorial here. Source code is available here.

A static topic map would not qualify as an adaptive network, but a dynamic, real time topic map system might have the characteristics of complex adaptive systems:

  • The number of elements is sufficiently large that conventional descriptions (e.g. a system of differential equations) are not only impractical, but cease to assist in understanding the system, the elements also have to interact and the interaction must be dynamic. Interactions can be physical or involve the exchange of information.
  • Such interactions are rich, i.e. any element in the system is affected by and affects several other systems.
  • The interactions are non-linear which means that small causes can have large results.
  • Interactions are primarily but not exclusively with immediate neighbours and the nature of the influence is modulated.
  • Any interaction can feed back onto itself directly or after a number of intervening stages, such feedback can vary in quality. This is known as recurrency.
  • Such systems are open and it may be difficult or impossible to define system boundaries
  • Complex systems operate under far from equilibrium conditions, there has to be a constant flow of energy to maintain the organization of the system
  • All complex systems have a history, they evolve and their past is co-responsible for their present behaviour
  • Elements in the system are ignorant of the behaviour of the system as a whole, responding only to what is available to it locally

The more dynamic the connections between networks, the closer we will move towards networks with the potential for adaptation.

That isn’t to say all networks will adapt at all or that those that do, will do it well.

Suspect adaption, like integration, is going to depend upon the amount of semantic information on hand.

You may also want to review: Largenet2: an object-oriented programming library for simulating large adaptive networks by Gerd Zschaler, and Thilo Gross. Bioinformatics (2013) 29 (2): 277-278. doi: 10.1093/bioinformatics/bts663

Robustness Elasticity in Complex Networks

Wednesday, July 11th, 2012

Robustness Elasticity in Complex Networks by Timothy C. Matisziw, Tony H. Grubesic, and Junyu Guo. (Matisziw TC, Grubesic TH, Guo J (2012) Robustness Elasticity in Complex Networks. PLoS ONE 7(7): e39788. doi:10.1371/journal.pone.0039788)

Abstract:

Network robustness refers to a network’s resilience to stress or damage. Given that most networks are inherently dynamic, with changing topology, loads, and operational states, their robustness is also likely subject to change. However, in most analyses of network structure, it is assumed that interaction among nodes has no effect on robustness. To investigate the hypothesis that network robustness is not sensitive or elastic to the level of interaction (or flow) among network nodes, this paper explores the impacts of network disruption, namely arc deletion, over a temporal sequence of observed nodal interactions for a large Internet backbone system. In particular, a mathematical programming approach is used to identify exact bounds on robustness to arc deletion for each epoch of nodal interaction. Elasticity of the identified bounds relative to the magnitude of arc deletion is assessed. Results indicate that system robustness can be highly elastic to spatial and temporal variations in nodal interactions within complex systems. Further, the presence of this elasticity provides evidence that a failure to account for nodal interaction can confound characterizations of complex networked systems.

As you might expect, I am reading this paper from the perspective of connections between nodes of information and not, for example, nodes on the Internet. I suspect it is particularly relevant for models of (or the lack thereof) information sharing between agencies for example.

With only anecdotal evidence about sharing, it isn’t possible to determine what structural, organization or other barriers are blocking the flow of information. Or what changes would result in the largest amount of effective information sharing. If shared information is mired at upper management levels, then it is of little use to actual analysts.

BTW, you can rest assured this work will not be used inappropriately:

Matisziw’s model was documented in the publicly available journal PLoS ONE. Making such a powerful tool widely available won’t be a danger, Matisziw said. To use his model, a network must be understood in detail. Since terrorists and other criminals don’t have access to enough data about the networks, they won’t be able to use the model to develop doomsday scenarios. [From: Cyberwarfare, Conservation and Disease Prevention Could Benefit from New Network Model, where I first saw this story.

Do terrorists develop anything other than “doomsday scenarios?” Or is that just PR? Like Y2K or the recent DNS issue. Everyone gets worked up, small bump, life goes on.

Lima on Networks

Thursday, May 24th, 2012

I saw a mention of RSA Animate – The Power of Networks by Manuel Lima over at Flowing Data.

A high speed chase through ideas but the artistry of the presentation and presenter make it hold together quite nicely.

Manuel makes the case that organization of information is more complex than trees. In fact, makes a good case for networks being a better model.

If that bothers you, you might want to cut Manuel some slack or perhaps even support the “network” (singular) model.

There are those of us who don’t think a single network is sufficient.

😉

Resources to review before viewing the video:

Science and Complexity – Warren Weaver (1948 – reprint): The paper that Manuel cites in his presentation.

Wikipedia – Complexity Not bad as Wikipedia entries go. At least a starting point.

Visual Complexity

Thursday, May 10th, 2012

Visual Complexity

Described by Manuel Lima (its creator) as:

VisualComplexity.com intends to be a unified resource space for anyone interested in the visualization of complex networks. The project’s main goal is to leverage a critical understanding of different visualization methods, across a series of disciplines, as diverse as Biology, Social Networks or the World Wide Web. I truly hope this space can inspire, motivate and enlighten any person doing research on this field.

Not all projects shown here are genuine complex networks, in the sense that they aren’t necessarily at the edge of chaos, or show an irregular and systematic degree of connectivity. However, the projects that apparently skip this class were chosen for two important reasons. They either provide advancement in terms of visual depiction techniques/methods or show conceptual uniqueness and originality in the choice of a subject. Nevertheless, all projects have one trait in common: the whole is always more than the sum of its parts.

The homepage is simply stunning.

BTW, Manuel is also the author of: Visual Complexity: Mapping Patterns of Information.

Complex Networks -> Local Networks

Saturday, April 21st, 2012

The Game of Go: A Complex Network post reminds us that complex networks, with care, can be decomposed into local networks.

From the post:

Using a database containing around 5 000 games played by professional and amateur go players in international tournaments, Bertrand Georgeot from the Theoretical Physics Laboratory (Université Toulouse III-Paul Sabatier/CNRS) and Olivier Giraud from the Laboratory of Theoretical Physics and Statistical Models (Université Paris-Sud/CNRS) applied network theory to this game of strategy. They constructed a network whose nodes are local patterns on the board, while the vertices (which represent the links) reflect the sequence of moves. This enabled them to recapture part of the local game strategy. In this game, where players place their stones at the intersections of a grid consisting of 19 vertical and 19 horizontal lines (making 361 intersections), the researchers studied local patterns of 9 intersections. They showed that the statistical frequency distribution of these patterns follows Zipf’s law, similar to the frequency distribution of words in a language.

Although the go network’s features resemble those of other real networks (social networks or the Internet), it has its own specific properties. While the most recent simulation programs already include statistical data from real games, albeit at a still basic level, these new findings should allow better modeling of this kind of board game.

The researchers did not even attempt to solve the entire board but rather looked for “local” patterns on the board.

What “local patterns” are you missing in “big data?”

Article reference: The game of go as a complex network. B. Georgeot and O. Giraud 2012 EPL 97 68002.

Abstract:

We study the game of go from a complex network perspective. We construct a directed network using a suitable definition of tactical moves including local patterns, and study this network for different datasets of professional and amateur games. The move distribution follows Zipf’s law and the network is scale free, with statistical peculiarities different from other real directed networks, such as, e.g., the World Wide Web. These specificities reflect in the outcome of ranking algorithms applied to it. The fine study of the eigenvalues and eigenvectors of matrices used by the ranking algorithms singles out certain strategic situations. Our results should pave the way to a better modelization of board games and other types of human strategic scheming.

The structure and function of complex networks (2003)

Friday, March 30th, 2012

The structure and function of complex networks by M. E. J. Newman (2003).

Abstract:

Inspired by empirical studies of networked systems such as the Internet, social networks, and biological networks, researchers have in recent years developed a variety of techniques and models to help us understand or predict the behavior of these systems. Here we review developments in this field, including such concepts as the small-world effect, degree distributions, clustering, network correlations, random graph models, models of network growth and preferential attachment, and dynamical processes taking place on networks.

Not the earliest survey of work on complex networks nor the latest but one that gives a good overview of the area. I will be citing later survey work on graphs and complex networks. Your pointers/suggestions are most welcome.

CNetS

Saturday, November 26th, 2011

CNetS: Center for Complex Networks and Systems Research

Work of the Center:

The types of problems that we work on include mining usage and traffic patterns in technological networks such as the Web and the Internet; studying the interaction between social dynamics and online behaviors; modeling the evolution of complex social and technological networks; developing adaptive, distributed, collaborative, agent-based applications for Web search and recommendation; understanding complex biological networks and complex reaction in biochemistry; developing models for the spread of diseases; understanding how coordinated behavior arises from the dynamical interaction of nervous system, body, and environment; studying social human behavior; exploring reasons underlying species diversity; studying the interplay between self-organization and natural selection; understanding how information arises and is used in biological systems; and so on. All these examples are characterized by complex nonlinear feedback mechanisms and it is now being increasingly recognized that the outcome of such interactions can only be understood through mathematical and computational models.

Lots of interesting content. I will be calling some of it out in the future.