Graph Entropy from Closed Walk and Cycle Functionals

详细信息    查看全文

• 关键词：Graph entropy ; Random walks ; Ihara coefficients
• 刊名：Lecture Notes in Computer Science
• 出版年：2016
• 出版时间：2016
• 年：2016
• 卷：10029
• 期：1
• 页码：174-184
• 全文大小：1,723 KB
• 参考文献：1.Dehmer, M.: Information processing in complex networks: graph entropy and information functionals. Appl. Math. Comput. 201, 82–94 (2008)MathSciNet MATH
  2.Estrada, E.: Characterization of 3D molecular structure. Chem. Phys. Lett. 319(5–6), 713–718 (2000)CrossRef
  3.Körner, J.: Coding of an information source having ambiguous alphabet and the entropy of graphs. In: 6th Prague Conference on Information Theory (1973)
  4.Kolmogorov, A.N.: Three approaches to the definition of the concept ? Quantity of information? Probl. Peredachi Informatsii 1(1), 3–11 (1965)MathSciNet MATH
  5.Chaitin, G.J.: On the length of programs for computing finite binary sequences. J. ACM 13(4), 547–569 (1966)MathSciNet CrossRef MATH
  6.Scott, G., Storm, C.: The coefficients of the Ihara zeta function. Involve - J. Math. 1(2), 217–233 (2008)MathSciNet CrossRef MATH
  7.Aziz, F., Wilson, R.C., Hancock, E.R.: Backtrackless walks on a graph. IEEE Trans. Neural Netw. Learn. Syst. 24(6), 977–989 (2013)CrossRef
  8.Ren, P., Wilson, R.C., Hancock, E.R.: Graph characterization via Ihara coefficients. IEEE Trans. Neural Netw. 22(2), 233–245 (2010)
  9.Escolano, F., Hancock, E.R., Lozano, M.A.: Heat diffusion: thermodynamic depth complexity of networks. Phys. Rev. E 85(3), 036206 (2012)CrossRef
  10.Erdõs, P., Rényi, A.: On the evolution of random graphs. Publ. Math. Inst. Hungar. Acad. Sci. 5, 17–61 (1960)MathSciNet MATH
  11.Watts, D.J., Strogatz, S.H.: Collective dynamics of ‘small-world’ networks. Nature 393, 440–442 (1998)CrossRef
  12.Barabási, A., Albert, R.: Emergence of scaling in random networks. Science 286, 509–512 (1999)MathSciNet CrossRef MATH
  13.Bass, H.: The Ihara-Selberg zeta function of a tree lattice. Int. J. Math. 3, 717–797 (1992)MathSciNet CrossRef MATH
  14.Kotani, M., Sunada, T.: Zeta function of finite graphs. J. Math. Univ. Tokyo 7(1), 7–25 (2000)MathSciNet MATH
  15.Delaunay, B.: Sur la sphre vide. Izvestia Akademii Nauk SSSR, Otdelenie Matematicheskikh i Estestvennykh Nauk 7, 793–800 (1934)MATH
  16.Toussaint, G.T.: The relative neighbourhood graph of a finite planar set. Pattern Recogn. 12, 261–268 (1980)MathSciNet CrossRef MATH
  17.Jolliffe, I.T.: Principal Component Analysis. Springer, New York (1986)CrossRef MATH
  18.Gabriel, K.R., Sokal, R.R.: A new statistical approach to geographic variation analysis. Syst. Zool. 12, 205–222 (1969)
  19.Harris, C., Stephens, M.: A combined corner and edge detector. In: Fourth Alvey Vision Conference, Manchester, UK, pp. 147–151 (1988)
  20.Nayar, S.K., Nene, S.A., Murase, H.: Columbia object image library (coil 100), Department of Comp. Science, Columbia University, Technical report, CUCS-006-96 (1996)
  
• 作者单位：Furqan Aziz (18)
  Edwin R. Hancock (19)
  Richard C. Wilson (19)
  
  18. Department of Computer Science, IM—Sciences, Peshawar, Pakistan
  19. Department of Computer Science, University of York, York, YO10 5GH, UK
  
• 丛书名：Structural, Syntactic, and Statistical Pattern Recognition
• ISBN：978-3-319-49055-7
• 刊物类别：Computer Science
• 刊物主题：Artificial Intelligence and Robotics
  Computer Communication Networks
  Software Engineering
  Data Encryption
  Database Management
  Computation by Abstract Devices
  Algorithm Analysis and Problem Complexity
  
• 出版者：Springer Berlin / Heidelberg
• ISSN：1611-3349
• 卷排序：10029

文摘

This paper presents an informational functional that can be used to characterise the entropy of a graph or network structure, using closed random walks and cycles. The work commences from Dehmer’s information functional, that characterises networks at the vertex level, and extends this to structures which capture the correlation of vertices, using walk and cycle structures. The resulting entropies are applied to synthetic networks and to network time series. Here they prove effective in discriminating between different types of network structure, and detecting changes in the structure of networks with time.