Reference : Complexity of Networks II: The Set Complexity of Edge-Colored Graphs
Scientific journals : Article
Physical, chemical, mathematical & earth Sciences : Multidisciplinary, general & others
Complexity of Networks II: The Set Complexity of Edge-Colored Graphs
Ignac, Tomasz mailto [University of Luxembourg > Luxembourg Centre for Systems Biomedicine (LCSB) > >]
Sakhanenko, N. A. [> >]
Galas, David J. [University of Luxembourg > Luxembourg Centre for Systems Biomedicine (LCSB) > >]
Wiley Online Library
Yes (verified by ORBilu)
[en] complexity of graphs ; mutual information ; biological networks ; set complexity ; similarity matrices and their spectra
[en] We previously introduced the concept of “set-complexity”, based on a context-dependent measure of information, and used this concept to describe the complexity of gene interaction networks. In the previous paper in this series we analyzed the set-complexity of binary graphs. Here we extend this analysis to graphs with multi-colored edges that more closely match biological structures like the gene interaction networks. All highly complex graphs by this measure exhibit a modular structure. A principal result of this work is that for the most complex graphs of a given size the number of edge colors is equal to the number of “modules” of the graph. Complete multipartite graphs (CMGs) are defined and analyzed, and the relation between complexity and structure of these graphs is examined in detail. We establish that the mutual information between any two nodes in a CMG can be fully expressed in terms of entropy, and present an explicit expression for the set complexity of CMGs (Theorem 3). An algorithm for generating highly complex graphs from CMGs is described. We establish several theorems relating these concepts and connecting complex graphs with a variety of practical network properties. In exploring the relation between symmetry and complexity we use the idea of a similarity matrix and its spectrum for highly complex graphs.
Luxembourg Centre for Systems Biomedicine (LCSB): Experimental Neurobiology (Balling Group) ; Luxembourg Centre for Systems Biomedicine (LCSB): Bioinformatics Core (R. Schneider Group)
in press

File(s) associated to this reference

Fulltext file(s):

Limited access
PSI main.pdfPublisher postprint1.23 MBRequest a copy

Bookmark and Share SFX Query

All documents in ORBilu are protected by a user license.