2.12 Network Complexity
Real-world networks are complex and rich in variety, as explained above; a measure of the structural complexity of networks (network complexity) is therefore necessary.
The “graph entropy” is often used to evaluate network complexity (reviewed in Refs. [45,46]). The graph entropy of network G is based on Shannon's entropy, and it is conceptually defined as
(2.47)
where |X| corresponds to a network invariant such as the total number of nodes or the total number of edges. The network is divided into n subsets, based on a given criterion, and the value |Xi| denotes the cardinality of subset i. A larger indicates a higher network-variation.
Here, as a simple example, we consider the graph entropy based on the node degree [47]. Let Nk be the number of nodes with degree k; the graph entropy is given as
(2.48)
Since Nk/N = P(k) (i.e., the degree distribution), this equation is rewritten as . That is, the graph entropy characterizes the degree of heterogeneity in a network. ...
Get Statistical and Machine Learning Approaches for Network Analysis now with the O’Reilly learning platform.
O’Reilly members experience books, live events, courses curated by job role, and more from O’Reilly and nearly 200 top publishers.