Beyond Graphs: Capturing Groups in Networks

摘要

Currently, the de facto representational choice for networks is graphs. A graph captures pairwise relationships (edges) between entities (vertices) in a network. Network science however, is replete with group relationships that are more than the sum of the pairwise relationships. For example, collaborative teams, wireless broadcast, insurgent cells, coalitions all contain unique group dynamics that need to be captured in their respective networks. We propose the use of the (abstract) simplicial complex to model groups in networks. We show that a number of problems within social and communications networks such as network-wide broadcast and collaborative teams can be elegantly captured using simplicial complexes in a way that is not possible with graphs. We formulate combinatorial optimization problems in these areas in a simplicial setting and illustrate the applicability of topological concepts such as 'Betti numbers' in structural analysis. As an illustrative case study, we present an analysis of a real-world collaboration network, namely the ARL NS-CTA network of researchers and tasks.