Complex Sciences. First International Conference, Complex 2009, Shanghai, China, February 23-25, 2009. Revised Papers, Part 1

Research Article

Characterizing the Structural Complexity of Real-World Complex Networks

Download
389 downloads
  • @INPROCEEDINGS{10.1007/978-3-642-02466-5_118,
        author={Jun Wang and Gregory Provan},
        title={Characterizing the Structural Complexity of Real-World Complex Networks},
        proceedings={Complex Sciences. First International Conference, Complex 2009, Shanghai, China, February 23-25, 2009. Revised Papers, Part 1},
        proceedings_a={COMPLEX PART 1},
        year={2012},
        month={5},
        keywords={Complex Networks Structural Complexity Random Graph Generators},
        doi={10.1007/978-3-642-02466-5_118}
    }
    
  • Jun Wang
    Gregory Provan
    Year: 2012
    Characterizing the Structural Complexity of Real-World Complex Networks
    COMPLEX PART 1
    Springer
    DOI: 10.1007/978-3-642-02466-5_118
Jun Wang1,*, Gregory Provan1,*
  • 1: University College Cork
*Contact email: jw8@cs.ucc.ie, g.provan@cs.ucc.ie

Abstract

Although recent research has shown that the complexity of a network depends on its structural organization, which is linked to the functional constraints the network must satisfy, there is still no systematic study on how to distinguish topological structure and measure the corresponding structural complexity of complex networks. In this paper, we propose the first consistent framework for distinguishing and measuring the structural complexity of real-world complex networks. In terms of the smallest of the model with high-order constraints necessary for fitting real networks, we can classify real-world networks into different structural complexity levels. We demonstrate the approach by measuring and classifying a variety of real-world networks, including biological and technological networks, small-world and non-small-world networks, and spatial and non-spatial networks.