Information indices with high discriminative power for graphs.

Area of Science:

• Graph Theory
• Information Theory
• Cheminformatics

Background:

• Graph-based information-theoretic measures are crucial for analyzing complex networks.
• Existing measures like the Balaban J index have limitations in capturing graph uniqueness.
• Topological descriptors play a vital role in understanding molecular structures and properties.

Purpose of the Study:

• To evaluate the uniqueness of information-theoretic measures for graphs using information functionals.
• To compare the performance of these novel measures against established indices, including the Balaban J index.
• To explore the efficacy of a degree-degree association-based information functional.

Main Methods:

• Generation of nearly 12 million non-isomorphic, unweighted graphs.
• Application of information functionals, specifically one based on degree-degree associations.
• Comparative analysis with the Balaban J index and other topological descriptors.
• Exploration using exhaustively generated sets of alkane trees (connected, acyclic graphs with vertex degree ≤ 4).

Main Results:

• The proposed information index, utilizing a degree-degree association functional, significantly outperforms the Balaban J index.
• Demonstrated superior uniqueness of the developed information-theoretic measure across a vast graph dataset.
• Gained deeper insights into the uniqueness of topological descriptors through analysis of alkane trees.

Conclusions:

• Information functionals, particularly those based on degree-degree associations, offer a powerful approach to graph uniqueness.
• The novel information index presents a more effective descriptor for graph analysis compared to the Balaban J index.
• This research provides a robust framework for developing and evaluating graph-based descriptors in various scientific domains.