指示されたグラフの近似フォンノイマンエントロピー

この論文では、指示されたグラフの構造的複雑さを評価するためのエントロピー測定を開発します。無向グラフの構造特性を定量化するための多くの既存の代替測定値がありますが、指示されたグラフの対応する測定値は比較的少ないです。文献のこのギャップを埋めるために、指示されたグラフに適用できる代替手法を探ります。指向グラフのラプラシアンのChungの一般化を使用して、Von Neumannエントロピーの計算を無向から指向グラフに拡張します。単純なノード内および級統計の観点から表現できるエントロピーの単純化された形式を提供します。さらに、弱い指示されたグラフの両方に適用され、ネットワーク構造を特徴付けるために使用できる、Von Neumannエントロピーのおおよその形式があります。タンパク質データベースや高エネルギー物理理論の引用ネットワークの構造を含む、人工および現実世界の両方のデータセットに関する本論文で定義されているこれらの単純化されたエントロピー形式の有用性を示します。

In this paper, we develop an entropy measure for assessing the structural complexity of directed graphs. Although there are many existing alternative measures for quantifying the structural properties of undirected graphs, there are relatively few corresponding measures for directed graphs. To fill this gap in the literature, we explore an alternative technique that is applicable to directed graphs. We commence by using Chung's generalization of the Laplacian of a directed graph to extend the computation of von Neumann entropy from undirected to directed graphs. We provide a simplified form of the entropy which can be expressed in terms of simple node in-degree and out-degree statistics. Moreover, we find approximate forms of the von Neumann entropy that apply to both weakly and strongly directed graphs, and that can be used to characterize network structure. We illustrate the usefulness of these simplified entropy forms defined in this paper on both artificial and real-world data sets, including structures from protein databases and high energy physics theory citation networks.