Article (Scientific journals)
Complexity of Networks II: The Set Complexity of Edge-Colored Graphs
Ignac, Tomasz; Sakhanenko, N. A.; Galas, David J.
2012In Complexity, 17 (5), p. 23-36
Peer Reviewed verified by ORBi
 

Files


Full Text
PSI main.pdf
Publisher postprint (1.26 MB)
Request a copy

All documents in ORBilu are protected by a user license.

Send to



Details



Keywords :
complexity of graphs; mutual information; biological networks; set complexity; similarity matrices and their spectra
Abstract :
[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.
Research center :
Luxembourg Centre for Systems Biomedicine (LCSB): Experimental Neurobiology (Balling Group)
- Luxembourg Centre for Systems Biomedicine (LCSB): Bioinformatics Core (R. Schneider Group)
Disciplines :
Physical, chemical, mathematical & earth Sciences: Multidisciplinary, general & others
Identifiers :
UNILU:UL-ARTICLE-2011-423
Author, co-author :
Ignac, Tomasz ;  University of Luxembourg > Luxembourg Centre for Systems Biomedicine (LCSB)
Sakhanenko, N. A.
Galas, David J. ;  University of Luxembourg > Luxembourg Centre for Systems Biomedicine (LCSB)
External co-authors :
yes
Language :
English
Title :
Complexity of Networks II: The Set Complexity of Edge-Colored Graphs
Publication date :
2012
Journal title :
Complexity
ISSN :
1099-0526
Publisher :
Wiley Online Library
Volume :
17
Issue :
5
Pages :
23-36
Peer reviewed :
Peer Reviewed verified by ORBi
Commentary :
in press
Available on ORBilu :
since 18 December 2013

Statistics


Number of views
46 (2 by Unilu)
Number of downloads
0 (0 by Unilu)

Scopus citations®
 
7
Scopus citations®
without self-citations
5
OpenCitations
 
8
WoS citations
 
7

Bibliography


Similar publications



Contact ORBilu