A new way of finding community structure within networks – anything from social networks such as Facebook, to power grids, political voting networks, and protein interaction networks in biology – could help us understand how people are connected and how connections change over time. The new technique, developed by a team from the University of North Carolina, University of Oxford, and Harvard University, aims to be more realistic than conventional approaches, which only capture one type of connection or a network at only one moment in time.
The new approach captures the totality of connections within a network and could be used to examine the different ways communities form; for example, analysing relationships between University students and staff across many different connections such as Facebook friendship, College affiliation, and subject studied. Alternatively, it could be used to track how one type of connection – such as Facebook friendship – changes over time.
The technique is not limited to social networks as community detection has the potential to find important groups in many other applications, such as protein-protein interaction networks, transportation networks, and political voting networks.
A report of the team’s work, advancing the theory of community detection, will be published in this week’s Science.
‘Capturing the complexity of people's relationships through networks such as Facebook and how these relationships change over time is a huge challenge,’ said Dr Mason Porter of Oxford University's Mathematical Institute, an author of the report. ‘Our new approach, which can be applied to any type of network, is potentially much better than existing methods at identifying what makes a 'community' within a network and at tracking how such groupings evolve over time.’
Until now, it was only possible to detect communities using computer algorithms in very special cases – in particular, only in networks that are treated as if they don't change over time and as if they have only one type of connection.
The new computational method can be used with what researchers call ‘multislice’ networks, in which each ‘slice’ might represent a social network at one snapshot in time or a different set of connections between the same set of individuals. These ‘slices’ are combined into a larger mathematical object, which can contain a potentially huge amount of data and is difficult to analyse. Previous community-finding methods could only deal with each slice separately, and it was necessary to compare the results obtained from different slices using ad hoc tools (if it was possible at all) and the new method overcomes this key challenge.
‘It's very easy to use ‘ad hoc’ methods and miss something that is potentially interesting or important in such complex networks,’ said Dr Porter. ‘Whilst our new approach doesn't dictate what you will find, it does potentially give you a much better chance of finding interesting connections if they're there.’
- A report of the research, entitled ‘Community Structure in Time-Dependent, Multiscale, and Multiplex Networks’, is published in Science on 14 May, embargoed until 19:00 BST/14:00 EST (US) 13 May 2010.
