Bipartite Structure of All Complex Networks

xholonWorkbook.xml

<?xml version="1.0" encoding="UTF-8"?>
<!--Xholon Workbook http://www.primordion.com/Xholon/gwt/ MIT License, Copyright (C) Ken Webb, Mon Dec 18 2017 10:49:05 GMT-0500 (EST)-->
<XholonWorkbook>

<Notes><![CDATA[
Xholon
------
Title: Bipartite Structure of All Complex Networks
Description: 
Url: http://www.primordion.com/Xholon/gwt/
InternalName: 0d59ec825e2da41d72214a8aab00e96f
Keywords: 

My Notes
--------
December 18, 2017

See also my "Hypergraphs" workbook:
https://gist.github.com/kenwebb/9e9aa6d9283efb51abb1983f52fa6d55

Clique
- perhaps this concept can help me explore the commonality between:
 - child-parent relationships
 - pack-cable relationships
  - Cell Model AO-PO (enyme-small molecule) bipartite relationship

References
----------
(1) Jean-Loup Guillaume, Matthieu Latapy. Bipartite Structure of All Complex Networks. Information
Processing Letters, Elsevier, 2004, 90, pp.Issue 5, Pages 215-221.
    https://hal-univ-diderot.archives-ouvertes.fr/hal-00016855/document
    ‎Cited by 208
    
    Abstract
    The analysis and modelling of various complex networks has received much at-
    tention in the last few years. Some such networks display a natural bipartite struc-
    ture: two kinds of nodes coexist with links only between nodes of different kinds.
    This bipartite structure has not been deeply studied until now, mainly because it
    appeared to be specific to only a few complex networks. However, we show here that
    all complex networks can be viewed as bipartite structures sharing some important
    statistics, like degree distributions. The basic properties of complex networks can
    be viewed as consequences of this underlying bipartite structure. This leads us to
    propose the first simple and intuitive model for complex networks which captures
    the main properties met in practice.
    
    In this communication, we show that all complex networks have an underlying bipartite structure.
    
    A bipartite network is a triple G = (⊤, ⊥, E) where ⊤ and ⊥ are two disjoint sets of
    nodes, respectively the top and bottom nodes, and E ⊆ ⊤ × ⊥ is the set of links of the network.
    The difference with classical (unipartite) networks lies in the fact that links exist only between top nodes and bottom nodes.

(2) https://en.wikipedia.org/wiki/Complex_network
    In the context of network theory, a complex network is a graph (network)
    with non-trivial topological features—features that do not occur in simple networks
    such as lattices or random graphs but often occur in graphs modelling of real systems.
    The study of complex networks is a young and active area of scientific research (since 2000)
    inspired largely by the empirical study of real-world networks such as computer networks,
    technological networks, brain networks and social networks.

(3) https://en.wikipedia.org/wiki/Clique_(graph_theory)
    In the mathematical area of graph theory, a clique is a subset of vertices of an undirected graph
    such that every two distinct vertices in the clique are adjacent; that is, its induced subgraph is complete.
    Cliques are one of the basic concepts of graph theory and are used in many other mathematical problems and constructions on graphs.
    A clique, C, in an undirected graph G = (V, E) is a subset of the vertices, C ⊆ V, such that every two distinct vertices are adjacent.
    This is equivalent to the condition that the induced subgraph of G induced by C is a complete graph.
    In some cases, the term clique may also refer to the subgraph directly.

(4) http://ai2-s2-pdfs.s3.amazonaws.com/81a4/7f57ae029f7413fa96a554e813348eb8ae40.pdf
    Basic notions for the analysis of large two-mode networks
    Matthieu Latapy, Clemence Magnien, Nathalie Del Vecchio, 2007

(5) Bipartite graphs as models of complex networks, Jean-Loup Guillaume and Matthieu Latapy

(6) http://onlinelibrary.wiley.com/doi/10.1111/2041-210X.12139/full
    A method for detecting modules in quantitative bipartite networks, Carsten F. Dormann, Rouven Strauss

(7) https://arxiv.org/pdf/0901.2384.pdf
    An Analysis of the Japanese Credit Network, G. De Masi, Y. Fujiwara, M. Gallegati, B. Greenwald, J. E. Stiglitz, 2010
    Many empirical studies have been conducted in the field of bipartite graphs . One can extract
    two networks from a bipartite network, each one composed by just one kind of nodes: these
    two networks are called projected networks, since they are obtained as a projection of the initial
    graph in the subspace composed by nodes of the same kind.

(8) https://pdfs.semanticscholar.org/3e75/ba4243cec50fa3ecf646098bfdd55d9aa437.pdf
    Data Reduction and Exact Algorithms for Clique, JENS GRAMM, JIONG GUO, FALK HUFFNER, and ROLF NIEDERMEIER, 2010
    To cover the edges of a graph with a minimum number of cliques is an NP-hard problem with many
    applications. We develop for this problem efficient and effective polynomial-time data reduction
    rules that, combined with a search tree algorithm, allow for exact problem solutions in competitive
    time. This is confirmed by experiments with real-world and synthetic data.

(9) https://arxiv.org/pdf/1203.1754.pdf
    Known algorithms for EDGE CLIQUE COVER are probably optimal, Marek Cygan, Marcin Pilipczuk, Michał Pilipczuk, 2012


]]></Notes> 

<_-.XholonClass>

  <!-- domain objects -->
  <PhysicalSystem/>
  <Block/>
  <Brick/>
  
  <!-- quantities -->
  <Height superClass="Quantity"/>
  
</_-.XholonClass>

<xholonClassDetails>
  <Block>
    <port name="height" connector="Height"/>
  </Block>
</xholonClassDetails>

<PhysicalSystem>
  <Block>
    <Height>0.1 m</Height>
  </Block>
  <Brick multiplicity="2"/>
</PhysicalSystem>

<Blockbehavior implName="org.primordion.xholon.base.Behavior_gwtjs"><![CDATA[
  var a = 123;
  var b = 456;
  var c = a * b;
  if (console) {
    console.log(c);
  }
]]></Blockbehavior>

<Heightbehavior implName="org.primordion.xholon.base.Behavior_gwtjs"><![CDATA[
  var myHeight, testing;
  var beh = {
    postConfigure: function() {
      testing = Math.floor(Math.random() * 10);
      myHeight = this.cnode.parent();
    },
    act: function() {
      myHeight.println(this.toString());
    },
    toString: function() {
      return "testing:" + testing;
    }
  }
]]></Heightbehavior>

<Brickbehavior implName="org.primordion.xholon.base.Behavior_gwtjs"><![CDATA[
  $wnd.xh.Brickbehavior = function Brickbehavior() {}

  $wnd.xh.Brickbehavior.prototype.postConfigure = function() {
    this.brick = this.cnode.parent();
    this.iam = " red brick";
  };

  $wnd.xh.Brickbehavior.prototype.act = function() {
    this.brick.println("I am a" + this.iam);
  };
]]></Brickbehavior>

<Brickbehavior implName="org.primordion.xholon.base.Behavior_gwtjs"><![CDATA[
  console.log("I'm another brick behavior");
]]></Brickbehavior>

<SvgClient><Attribute_String roleName="svgUri"><![CDATA[data:image/svg+xml,
<svg width="100" height="50" xmlns="http://www.w3.org/2000/svg">
  <g>
    <title>Block</title>
    <rect id="PhysicalSystem/Block" fill="#98FB98" height="50" width="50" x="25" y="0"/>
    <g>
      <title>Height</title>
      <rect id="PhysicalSystem/Block/Height" fill="#6AB06A" height="50" width="10" x="80" y="0"/>
    </g>
  </g>
</svg>
]]></Attribute_String><Attribute_String roleName="setup">${MODELNAME_DEFAULT},${SVGURI_DEFAULT}</Attribute_String></SvgClient>

</XholonWorkbook>