View in EDS

Offdiagonal complexity: A computationally quick complexity measure for graphs and networks

Saved in:
Bibliographic Details
Title: Offdiagonal complexity: A computationally quick complexity measure for graphs and networks
Authors: Claussen, Jens Christian1 claussen@theo-physik.uni-kiel.de
Source: Physica A. Feb2007, Vol. 375 Issue 1, p365-373. 9p.
Subjects: Random graphs, Linear algebra, Topology, Thermodynamics
Abstract: Abstract: A vast variety of biological, social, and economical networks shows topologies drastically differing from random graphs; yet the quantitative characterization remains unsatisfactory from a conceptual point of view. Motivated from the discussion of small scale-free networks, a biased link distribution entropy is defined, which takes an extremum for a power-law distribution. This approach is extended to the node–node link cross-distribution, whose nondiagonal elements characterize the graph structure beyond link distribution, cluster coefficient and average path length. From here a simple (and computationally cheap) complexity measure can be defined. This offdiagonal complexity (OdC) is proposed as a novel measure to characterize the complexity of an undirected graph, or network. While both for regular lattices and fully connected networks OdC is zero, it takes a moderately low value for a random graph and shows high values for apparently complex structures as scale-free networks and hierarchical trees. The OdC approach is applied to the Helicobacter pylori protein interaction network and randomly rewired surrogates. [Copyright &y& Elsevier]
Copyright of Physica A is the property of Elsevier B.V. and its content may not be copied or emailed to multiple sites without the copyright holder's express written permission. Additionally, content may not be used with any artificial intelligence tools or machine learning technologies. However, users may print, download, or email articles for individual use. This abstract may be abridged. No warranty is given about the accuracy of the copy. Users should refer to the original published version of the material for the full abstract. (Copyright applies to all Abstracts.)
Database: Engineering Source
FullText Text:
  Availability: 0
Header DbId: egs
DbLabel: Engineering Source
An: 23281027
AccessLevel: 6
PubType: Academic Journal
PubTypeId: academicJournal
PreciseRelevancyScore: 0
IllustrationInfo
Items – Name: Title
  Label: Title
  Group: Ti
  Data: Offdiagonal complexity: A computationally quick complexity measure for graphs and networks
– Name: Author
  Label: Authors
  Group: Au
  Data: <searchLink fieldCode="AR" term="%22Claussen%2C+Jens+Christian%22">Claussen, Jens Christian</searchLink><relatesTo>1</relatesTo><i> claussen@theo-physik.uni-kiel.de</i>
– Name: TitleSource
  Label: Source
  Group: Src
  Data: <searchLink fieldCode="JN" term="%22Physica+A%22">Physica A</searchLink>. Feb2007, Vol. 375 Issue 1, p365-373. 9p.
– Name: Subject
  Label: Subjects
  Group: Su
  Data: <searchLink fieldCode="DE" term="%22Random+graphs%22">Random graphs</searchLink><br /><searchLink fieldCode="DE" term="%22Linear+algebra%22">Linear algebra</searchLink><br /><searchLink fieldCode="DE" term="%22Topology%22">Topology</searchLink><br /><searchLink fieldCode="DE" term="%22Thermodynamics%22">Thermodynamics</searchLink>
– Name: Abstract
  Label: Abstract
  Group: Ab
  Data: Abstract: A vast variety of biological, social, and economical networks shows topologies drastically differing from random graphs; yet the quantitative characterization remains unsatisfactory from a conceptual point of view. Motivated from the discussion of small scale-free networks, a biased link distribution entropy is defined, which takes an extremum for a power-law distribution. This approach is extended to the node–node link cross-distribution, whose nondiagonal elements characterize the graph structure beyond link distribution, cluster coefficient and average path length. From here a simple (and computationally cheap) complexity measure can be defined. This offdiagonal complexity (OdC) is proposed as a novel measure to characterize the complexity of an undirected graph, or network. While both for regular lattices and fully connected networks OdC is zero, it takes a moderately low value for a random graph and shows high values for apparently complex structures as scale-free networks and hierarchical trees. The OdC approach is applied to the Helicobacter pylori protein interaction network and randomly rewired surrogates. [Copyright &y& Elsevier]
– Name: AbstractSuppliedCopyright
  Label:
  Group: Ab
  Data: <i>Copyright of Physica A is the property of Elsevier B.V. and its content may not be copied or emailed to multiple sites without the copyright holder's express written permission. Additionally, content may not be used with any artificial intelligence tools or machine learning technologies. However, users may print, download, or email articles for individual use. This abstract may be abridged. No warranty is given about the accuracy of the copy. Users should refer to the original published version of the material for the full abstract.</i> (Copyright applies to all Abstracts.)
PLink https://search.ebscohost.com/login.aspx?direct=true&site=eds-live&db=egs&AN=23281027
RecordInfo BibRecord:
  BibEntity:
    Identifiers:
      – Type: doi
        Value: 10.1016/j.physa.2006.08.067
    Languages:
      – Code: eng
        Text: English
    PhysicalDescription:
      Pagination:
        PageCount: 9
        StartPage: 365
    Subjects:
      – SubjectFull: Random graphs
        Type: general
      – SubjectFull: Linear algebra
        Type: general
      – SubjectFull: Topology
        Type: general
      – SubjectFull: Thermodynamics
        Type: general
    Titles:
      – TitleFull: Offdiagonal complexity: A computationally quick complexity measure for graphs and networks
        Type: main
  BibRelationships:
    HasContributorRelationships:
      – PersonEntity:
          Name:
            NameFull: Claussen, Jens Christian
    IsPartOfRelationships:
      – BibEntity:
          Dates:
            – D: 15
              M: 02
              Text: Feb2007
              Type: published
              Y: 2007
          Identifiers:
            – Type: issn-print
              Value: 03784371
          Numbering:
            – Type: volume
              Value: 375
            – Type: issue
              Value: 1
          Titles:
            – TitleFull: Physica A
              Type: main
ResultId 1