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
scite shows how a scientific paper has been cited by providing the context of the citation, a classification describing whether it supports, mentions, or contrasts the cited claim, and a label indicating in which section the citation was made.
Bibliography
Similar publications
Sorry the service is unavailable at the moment. Please try again later.