Upper and lower bounds for the q-entropy of network models with application to network model selection

详细信息    查看全文

• 作者：Mostafa Haghir Chehreghani ; ^{mostafa.chehreghani@gmail.com} ; Talel Abdessalem ^{talel.abdessalem@telecom-paristech.fr}
• 关键词：Graph algorithms ; Q-entropy ; Barabasi&ndash ; Albert model ; Small-world model ; Network model selection
• 刊名：Information Processing Letters
• 出版年：2017
• 出版时间：March 2017
• 年：2017
• 卷：119
• 期：Complete
• 页码：1-8
• 全文大小：435 K
• 卷排序：119

文摘

Graphs are important tools for modeling data in different biological, social and technological domains. The measurement of their complexity has theoretical and practical applications in many areas such as pattern recognition, graph clustering, network inference and network analysis. A widely used measure is the q-entropy. While this measure has extensively been studied for Erdos–Renyi (ER) random graphs, only few results have been reported for real-world networks that are typically scale-free or small-world graphs. In this paper, we study the q-entropy of scale-free graphs (generated by the Barabasi–Albert model) and small-world graphs (generated by the Watts–Strogatz model). We derive upper and lower bounds for the q-entropy and confirm our analytical studies by numerical simulations. We study the effect of the network parameters on the q-entropy for both scale-free and small-world graphs which yields to reveal some novel and interesting insights. For example, we show that the q-entropy of a Barabasi–Albert graph is usually larger than the q-entropy of a small-world graph with the same size and density, independent of the randomness degree of the small-world graph. We use the derived bounds as characteristics of real-world networks as well as network models. Therefore, based on the derived bounds, we propose a network model selection algorithm, that given a real-world network and a set of models, determines which of the models most likely generates the real-world network.