Network Analysis and Visualisation

Recent technological advances produce a lot of data, and have led to many large and complex network models in many application domains; examples include:

1. Webgraphs: They are huge: the whole graph consists of billions of nodes.
2. Software engineering: Large-scale software engineering deals with very large sets of software modules and relationships between them. Analysis of such networks is essential for design, performance tuning, and refactoring legacy code.
3. Biological networks: Protein-protein interaction (PPI) networks, metabolic pathways, gene regulatory networks and phylogenetic networks are used by biologists to analyse and engineer biochemical materials. In general they have up to thousands of nodes. However, their relationship is very complex.
4. Social networks: These include telephone call graphs (used to trace terrorists), money movement networks (used to detect money laundering), and sexual contact graphs (used to analyse epidemics). The size of the network can be medium to very large.

Understanding these networks is a key enabler for many applications.

Good analysis methods are needed for these networks, and some are available. However, such methods are not useful unless the results are effectively communicated to humans. Visualisation can be an effective tool for the understanding of such networks. Good visualisation reveals the hidden structure of the networks and amplifies human understanding, thus leading to new insights, new findings and possible predictions for the future.

A critical issue for both analysis and visualisation is scale. Existing methods do not scale well enough to be effective on current data sets. Data sets such as telephone call graphs, and protein-protein interaction networks are growing at a rate that is considerably faster than our ability to gain an understanding of them. Existing analysis and visualisation methods fail to deal with data complexity, for real world data sets. Further, human perception and cognition is limited. For example, when using large mega-pixel displays, the human brain still fails to deal with the visual complexity. Visualisation researchers need to reduce the data set to overcome visual complexity.

The main outcome of the taskforce will be continuing and cross-disciplinary research with a common theme of analysis and visualisation for large and complex networks.

Analysis and visualisation of large and complex networks is a challenging research topic. For example, the current hot topics in Social Network Analysis are scale-free networks (at the fundamental level) and terrorist networks (at the application level). More specifically we can identify the following research significance:

Scalability: the main challenge of this research is scalability. For example, webgraphs or telephone call graphs gathered by AT&T have billions of nodes. Does it make sense to visualise the whole graph? The use of large display methods provides a partial solution. In some cases, it is impossible to visualise the whole graph. In many cases, one cannot possibly load the whole graph in a main memory. Hence, the design of new analysis and visualisation methods for huge networks is a key research challenge for research from databases to computer graphics.

Complexity: the second challenge for this taskforce is complexity. Relationships between actors in a social network, for example, can have a multitude of attributes (for example, observed behavior can be "confirmed" or "unconfirmed", relationships can be directed or undirected, and weighted by probabilities). Also, biological networks are quite complex in nature; metabolic pathways have only a few thousand nodes, but their relationships and interactions are very complex; for example, the data may be "given" by nature, but some parts of the data may be "unknown" to human scientists. The design of analysis and visualisation methods to resolve these complexity issues is the second research challenge.

Integration of visualisation with analysis: Analysis tools for networks are not useful without visualisation, and visualisation tools are not useful unless they are linked to analysis. This integration of analysis and visualisation of large and complex networks will be the third research challenge.

Network Dynamics: Real world networks are always changing over time. Many social networks, such as webgraphs, evolve relatively slowly over time. In some cases, such as telephone call networks, the data is a very fast-streamed graph. Effective and efficient modeling, analysis and visualisation for dynamic networks are challenging research topics.

The short-term impact of this task force will be an Australian research effort to solve problems in the analysis and visualisation of large and complex networks. The aim is to involve early career researchers, and to assist them in academic and industrial research. For the long term, we hope that this task force will be the beginning of an Australian industry in providing software solutions to these problems.

The followings are core participants from EII Network:

Other core participants outside EII Network include:

1. Data Mining: Sanjay Chawla (Usyd)
2. Information System: Byunggu Choi (Usyd)
3. Network Optimisation: Hiroshi Nagamochi (Kyoto U)
4. Network Theory: Miro Kraetzel (DSTO)
5. Sociology/Psychology: Pip Pattison, Garry Robins (Umelb)
6. Biology: Peter Little, Rohan Williams (UNSW)