ABSTRACT
In this paper, we define novel graph measures for directed networks. The measures are based on graph polynomials utilizing the out- and in-degrees of directed graphs. Based on these polynomial, we define another polynomial and use their positive zeros as graph measures. The measures have meaningful properties that we investigate based on analytical and numerical results. As the computational complexity to compute the measures is polynomial, our approach is efficient and can be applied to large networks. We emphasize that our approach clearly complements the literature in this field as, to the best of our knowledge, existing complexity measures for directed graphs have never been applied on a large scale.
Subject(s)
Computational Biology/statistics & numerical data , Computer Graphics/statistics & numerical data , Computer Simulation , Game Theory , Mathematical Concepts , Systems Biology/statistics & numerical dataABSTRACT
In this paper, we study several distance-based entropy measures on fullerene graphs. These include the topological information content of a graph I a ( G ) , a degree-based entropy measure, the eccentric-entropy I f σ ( G ) , the Hosoya entropy H ( G ) and, finally, the radial centric information entropy H e c c . We compare these measures on two infinite classes of fullerene graphs denoted by A 12 n + 4 and B 12 n + 6 . We have chosen these measures as they are easily computable and capture meaningful graph properties. To demonstrate the utility of these measures, we investigate the Pearson correlation between them on the fullerene graphs.
ABSTRACT
In this paper, we introduce the Hosoya-Spectral indices and the Hosoya information content of a graph. The first measure combines structural information captured by partial Hosoya polynomials and graph spectra. The latter is a graph entropy measure which is based on blocks consisting of vertices with the same partial Hosoya polynomial. We evaluate the discrimination power of these quantities by interpreting numerical results.
Subject(s)
Models, Theoretical , Algorithms , Computer Graphics , Pattern Recognition, Automated/methodsABSTRACT
In this paper, we evaluate the discrimination power of structural superindices. Superindices for graphs represent measures composed of other structural indices. In particular, we compare the discrimination power of the superindices with those of individual graph descriptors. In addition, we perform a statistical analysis to generalize our findings to large graphs.
Subject(s)
Algorithms , Models, Chemical , Models, Statistical , Humans , Image Processing, Computer-Assisted , Random Allocation , Sensitivity and SpecificityABSTRACT
This paper explores relationships between classical and parametric measures of graph (or network) complexity. Classical measures are based on vertex decompositions induced by equivalence relations. Parametric measures, on the other hand, are constructed by using information functions to assign probabilities to the vertices. The inequalities established in this paper relating classical and parametric measures lay a foundation for systematic classification of entropy-based measures of graph complexity.