Graph entropy

<h2 id="definition">Definition</h2>
<p>Let 
  
    
      
        G
        =
        (
        V
        ,
        E
        )
      
    
    {\displaystyle G=(V,E)}
  
 be an <a href="/facts/Undirected_graph/kw3eIBUe">undirected graph</a>. The graph entropy of 
  
    
      
        G
      
    
    {\displaystyle G}
  
, denoted 
  
    
      
        H
        (
        G
        )
      
    
    {\displaystyle H(G)}
  
 is defined as
</p>

H
        (
        G
        )
        =
        
          min
          
            X
            ,
            Y
          
        
        I
        (
        X
        ;
        Y
        )
      
    
    {\displaystyle H(G)=\min _{X,Y}I(X;Y)}

<p>where 
  
    
      
        X
      
    
    {\displaystyle X}
  
 is chosen <a href="/facts/Discrete_uniform_distribution/M52SQP5n">uniformly</a> from 
  
    
      
        V
      
    
    {\displaystyle V}
  
, 
  
    
      
        Y
      
    
    {\displaystyle Y}
  
 ranges over <a href="/facts/Independent_set_(graph_theory)/ksu46kdz">independent sets</a> of G, the joint distribution of 
  
    
      
        X
      
    
    {\displaystyle X}
  
 and 
  
    
      
        Y
      
    
    {\displaystyle Y}
  
 is such that 
  
    
      
        X
        ∈
        Y
      
    
    {\displaystyle X\in Y}
  
 with probability one, and 
  
    
      
        I
        (
        X
        ;
        Y
        )
      
    
    {\displaystyle I(X;Y)}
  
 is the <a href="/facts/Mutual_information/HIUvsjvV">mutual information</a> of 
  
    
      
        X
      
    
    {\displaystyle X}
  
 and 
  
    
      
        Y
      
    
    {\displaystyle Y}
  
.<a class="footnote-ref" id="fnref:5" href="#fn:5"><sup>5</sup></a> 
</p><p>That is, if we let 
  
    
      
        
          
            I
          
        
      
    
    {\displaystyle {\mathcal {I}}}
  
 denote the independent vertex sets in 
  
    
      
        G
      
    
    {\displaystyle G}
  
, we wish to find the joint distribution 
  
    
      
        X
        ,
        Y
      
    
    {\displaystyle X,Y}
  
 on 
  
    
      
        V
        ×
        
          
            I
          
        
      
    
    {\displaystyle V\times {\mathcal {I}}}
  
 with the lowest mutual information such that (i) the marginal distribution of the first term is uniform and (ii) in samples from the distribution, the second term contains the first term almost surely. The mutual information of 
  
    
      
        X
      
    
    {\displaystyle X}
  
 and 
  
    
      
        Y
      
    
    {\displaystyle Y}
  
 is then called the entropy of 
  
    
      
        G
      
    
    {\displaystyle G}
  
.
</p>
<h2 id="properties">Properties</h2>
<ul><li>Monotonicity. If 
  
    
      
        
          G
          
            1
          
        
      
    
    {\displaystyle G_{1}}
  
 is a subgraph of 
  
    
      
        
          G
          
            2
          
        
      
    
    {\displaystyle G_{2}}
  
 on the same vertex set, then 
  
    
      
        H
        (
        
          G
          
            1
          
        
        )
        ≤
        H
        (
        
          G
          
            2
          
        
        )
      
    
    {\displaystyle H(G_{1})\leq H(G_{2})}
  
.</li>
<li>Subadditivity. Given two graphs 
  
    
      
        
          G
          
            1
          
        
        =
        (
        V
        ,
        
          E
          
            1
          
        
        )
      
    
    {\displaystyle G_{1}=(V,E_{1})}
  
 and 
  
    
      
        
          G
          
            2
          
        
        =
        (
        V
        ,
        
          E
          
            2
          
        
        )
      
    
    {\displaystyle G_{2}=(V,E_{2})}
  
 on the same set of vertices, the <a href="/facts/Graph_operations/5po6Cfac">graph union</a> 
  
    
      
        
          G
          
            1
          
        
        ∪
        
          G
          
            2
          
        
        =
        (
        V
        ,
        
          E
          
            1
          
        
        ∪
        
          E
          
            2
          
        
        )
      
    
    {\displaystyle G_{1}\cup G_{2}=(V,E_{1}\cup E_{2})}
  
 satisfies 
  
    
      
        H
        (
        
          G
          
            1
          
        
        ∪
        
          G
          
            2
          
        
        )
        ≤
        H
        (
        
          G
          
            1
          
        
        )
        +
        H
        (
        
          G
          
            2
          
        
        )
      
    
    {\displaystyle H(G_{1}\cup G_{2})\leq H(G_{1})+H(G_{2})}
  
.</li>
<li>Arithmetic mean of disjoint unions. Let 
  
    
      
        
          G
          
            1
          
        
        ,
        
          G
          
            2
          
        
        ,
        ⋯
        ,
        
          G
          
            k
          
        
      
    
    {\displaystyle G_{1},G_{2},\cdots ,G_{k}}
  
 be a sequence of graphs on disjoint sets of vertices, with 
  
    
      
        
          n
          
            1
          
        
        ,
        
          n
          
            2
          
        
        ,
        ⋯
        ,
        
          n
          
            k
          
        
      
    
    {\displaystyle n_{1},n_{2},\cdots ,n_{k}}
  
 vertices, respectively. Then 
  
    
      
        H
        (
        
          G
          
            1
          
        
        ∪
        
          G
          
            2
          
        
        ∪
        ⋯
        
          G
          
            k
          
        
        )
        =
        
          
            
              1
              
                
                  ∑
                  
                    i
                    =
                    1
                  
                  
                    k
                  
                
                
                  n
                  
                    i
                  
                
              
            
          
        
        
          ∑
          
            i
            =
            1
          
          
            k
          
        
        
          
            n
            
              i
            
          
          H
          (
          
            G
            
              i
            
          
          )
        
      
    
    {\displaystyle H(G_{1}\cup G_{2}\cup \cdots G_{k})={\tfrac {1}{\sum _{i=1}^{k}n_{i}}}\sum _{i=1}^{k}{n_{i}H(G_{i})}}
  
.</li></ul>
<p>Additionally, simple formulas exist for certain families classes of graphs.
</p>
<ul><li>Complete balanced <a href="/facts/Multipartite_graph/dkylvqYK">k-partite graphs</a> have entropy 
  
    
      
        
          log
          
            2
          
        
        ⁡
        k
      
    
    {\displaystyle \log _{2}k}
  
. In particular,
<ul><li>Edge-less graphs have entropy 
  
    
      
        0
      
    
    {\displaystyle 0}
  
.</li>
<li><a href="/facts/Complete_graph/AYD6hUqI">Complete graphs</a> on 
  
    
      
        n
      
    
    {\displaystyle n}
  
 vertices have entropy 
  
    
      
        
          log
          
            2
          
        
        ⁡
        n
      
    
    {\displaystyle \log _{2}n}
  
.</li>
<li>Complete balanced <a href="/facts/Bipartite_graphs/xWcXV9MB">bipartite graphs</a> have entropy 
  
    
      
        1
      
    
    {\displaystyle 1}
  
.</li></ul></li>
<li>Complete <a href="/facts/Bipartite_graphs/xWcXV9MB">bipartite graphs</a> with 
  
    
      
        n
      
    
    {\displaystyle n}
  
 vertices in one partition and 
  
    
      
        m
      
    
    {\displaystyle m}
  
 in the other have entropy 
  
    
      
        H
        
          (
          
            
              n
              
                m
                +
                n
              
            
          
          )
        
      
    
    {\displaystyle H\left({\frac {n}{m+n}}\right)}
  
, where 
  
    
      
        H
      
    
    {\displaystyle H}
  
 is the <a href="/facts/Binary_entropy_function/s9cwzz4n">binary entropy function</a>.</li></ul>
<h2 id="example">Example</h2>
<p>Here, we use properties of graph entropy to provide a simple proof that a complete graph 
  
    
      
        G
      
    
    {\displaystyle G}
  
 on 
  
    
      
        n
      
    
    {\displaystyle n}
  
 vertices cannot be expressed as the union of fewer than 
  
    
      
        
          log
          
            2
          
        
        ⁡
        n
      
    
    {\displaystyle \log _{2}n}
  
 bipartite graphs.
</p><p><i>Proof</i> By monotonicity, no bipartite graph can have graph entropy greater than that of a complete bipartite graph, which is bounded by 
  
    
      
        1
      
    
    {\displaystyle 1}
  
. Thus, by sub-additivity, the union of 
  
    
      
        k
      
    
    {\displaystyle k}
  
 bipartite graphs cannot have entropy greater than 
  
    
      
        k
      
    
    {\displaystyle k}
  
. Now let 
  
    
      
        G
        =
        (
        V
        ,
        E
        )
      
    
    {\displaystyle G=(V,E)}
  
 be a complete graph on 
  
    
      
        n
      
    
    {\displaystyle n}
  
 vertices. By the properties listed above, 
  
    
      
        H
        (
        G
        )
        =
        
          log
          
            2
          
        
        ⁡
        n
      
    
    {\displaystyle H(G)=\log _{2}n}
  
. Therefore, the union of fewer than 
  
    
      
        
          log
          
            2
          
        
        ⁡
        n
      
    
    {\displaystyle \log _{2}n}
  
 bipartite graphs cannot have the same entropy as 
  
    
      
        G
      
    
    {\displaystyle G}
  
, so 
  
    
      
        G
      
    
    {\displaystyle G}
  
 cannot be expressed as such a union. 
  
    
      
        ◼
      
    
    {\displaystyle \blacksquare }

</p>
<h2 id="general-references">General References</h2>
<ul><li>Matthias Dehmer; Frank Emmert-Streib; Zengqiang Chen; Xueliang Li; Yongtang Shi (25 July 2016). <a href="https://books.google.com/books?id=CZ-_DAAAQBAJ"><i>Mathematical Foundations and Applications of Graph Entropy</i></a>. Wiley. <a href="/facts/ISBN_(identifier)/15AdSPa9">ISBN</a> 978-3-527-69325-2.</li></ul>
<h2 id="notes">Notes</h2>

<h2 id="references">References</h2>

<ol>
<li id="fn:1"><p>Matthias Dehmer; Abbe Mowshowitz; Frank Emmert-Streib (21 June 2013). Advances in Network Complexity. John Wiley & Sons. pp. 186–. ISBN 978-3-527-67048-2. <a href="978-3-527-67048-2" target="_blank">978-3-527-67048-2</a> <a href="#fnref:1" class="footnote-back-ref">↩</a></p></li>
<li id="fn:2"><p>Körner, János (1973). "Coding of an information source having ambiguous alphabet and the entropy of graphs". 6th Prague Conference on Information Theory: 411–425. <a href="#fnref:2" class="footnote-back-ref">↩</a></p></li>
<li id="fn:3"><p>Niels da Vitoria Lobo; Takis Kasparis; Michael Georgiopoulos (24 November 2008). Structural, Syntactic, and Statistical Pattern Recognition: Joint IAPR International Workshop, SSPR & SPR 2008, Orlando, USA, December 4-6, 2008. Proceedings. Springer Science & Business Media. pp. 237–. ISBN 978-3-540-89688-3. <a href="978-3-540-89688-3" target="_blank">978-3-540-89688-3</a> <a href="#fnref:3" class="footnote-back-ref">↩</a></p></li>
<li id="fn:4"><p>Bernadette Bouchon; Lorenza Saitta; Ronald R. Yager (8 June 1988). Uncertainty and Intelligent Systems: 2nd International Conference on Information Processing and Management of Uncertainty in Knowledge Based Systems IPMU '88. Urbino, Italy, July 4-7, 1988. Proceedings. Springer Science & Business Media. pp. 112–. ISBN 978-3-540-19402-6. <a href="978-3-540-19402-6" target="_blank">978-3-540-19402-6</a> <a href="#fnref:4" class="footnote-back-ref">↩</a></p></li>
<li id="fn:5"><p>G. Simonyi, "Perfect graphs and graph entropy. An updated survey," Perfect Graphs, John Wiley and Sons (2001) pp. 293-328, Definition 2” <a href="#fnref:5" class="footnote-back-ref">↩</a></p></li>
</ol>

Graph entropy open-in-new

Graph entropy