1
|
Wang J, Hancock ER. The Ihara zeta function as a partition function for network structure characterisation. Sci Rep 2024; 14:18386. [PMID: 39117698 PMCID: PMC11310400 DOI: 10.1038/s41598-024-68882-x] [Citation(s) in RCA: 0] [Impact Index Per Article: 0] [Reference Citation Analysis] [Abstract] [Key Words] [Track Full Text] [Journal Information] [Subscribe] [Scholar Register] [Received: 01/07/2024] [Accepted: 07/29/2024] [Indexed: 08/10/2024] Open
Abstract
Statistical characterizations of complex network structures can be obtained from both the Ihara Zeta function (in terms of prime cycle frequencies) and the partition function from statistical mechanics. However, these two representations are usually regarded as separate tools for network analysis, without exploiting the potential synergies between them. In this paper, we establish a link between the Ihara Zeta function from algebraic graph theory and the partition function from statistical mechanics, and exploit this relationship to obtain a deeper structural characterisation of network structure. Specifically, the relationship allows us to explore the connection between the microscopic structure and the macroscopic characterisation of a network. We derive thermodynamic quantities describing the network, such as entropy, and show how these are related to the frequencies of prime cycles of various lengths. In particular, the n-th order partial derivative of the Ihara Zeta function can be used to compute the number of prime cycles in a network, which in turn is related to the partition function of Bose-Einstein statistics. The corresponding derived entropy allows us to explore a phase transition in the network structure with critical points at high and low-temperature limits. Numerical experiments and empirical data are presented to evaluate the qualitative and quantitative performance of the resulting structural network characterisations.
Collapse
Affiliation(s)
- Jianjia Wang
- School of AI and Advanced Computing, Xi'an Jiaotong-Liverpool University, Suzhou, 215412, China.
| | - Edwin R Hancock
- Department of Computer Science, University of York, York, YO10 5GH, UK
| |
Collapse
|
2
|
|
3
|
Bahonar H, Mirzaei A, Sadri S, Wilson RC. Graph Embedding Using Frequency Filtering. IEEE TRANSACTIONS ON PATTERN ANALYSIS AND MACHINE INTELLIGENCE 2021; 43:473-484. [PMID: 31369368 DOI: 10.1109/tpami.2019.2929519] [Citation(s) in RCA: 0] [Impact Index Per Article: 0] [Reference Citation Analysis] [Abstract] [Track Full Text] [Subscribe] [Scholar Register] [Indexed: 06/10/2023]
Abstract
The target of graph embedding is to embed graphs in vector space such that the embedded feature vectors follow the differences and similarities of the source graphs. In this paper, a novel method named Frequency Filtering Embedding (FFE) is proposed which uses graph Fourier transform and Frequency filtering as a graph Fourier domain operator for graph feature extraction. Frequency filtering amplifies or attenuates selected frequencies using appropriate filter functions. Here, heat, anti-heat, part-sine and identity filter sets are proposed as the filter functions. A generalized version of FFE named GeFFE is also proposed by defining pseudo-Fourier operators. This method can be considered as a general framework for formulating some previously defined invariants in other works by choosing a suitable filter bank and defining suitable pseudo-Fourier operators. This flexibility empowers GeFFE to adapt itself to the properties of each graph dataset unlike the previous spectral embedding methods and leads to superior classification accuracy relative to the others. Utilizing the proposed part-sine filter set, which its members filter different parts of the spectrum in turn, improves the classification accuracy of GeFFE method. Additionally, GeFFE resolves the cospectrality problem entirely in tested datasets.
Collapse
|
4
|
|
5
|
Mellor A, Grusovin A. Graph comparison via the nonbacktracking spectrum. Phys Rev E 2019; 99:052309. [PMID: 31212453 DOI: 10.1103/physreve.99.052309] [Citation(s) in RCA: 4] [Impact Index Per Article: 0.8] [Reference Citation Analysis] [Abstract] [Track Full Text] [Journal Information] [Subscribe] [Scholar Register] [Received: 12/12/2018] [Indexed: 11/07/2022]
Abstract
The comparison of graphs is a vitally important, yet difficult task which arises across a number of diverse research areas including biological and social networks. There have been a number of approaches to define graph distance, however, often these are not metrics (rendering standard data-mining techniques infeasible) or are computationally infeasible for large graphs. In this work we define a new pseudometric based on the spectrum of the nonbacktracking graph operator and show that it cannot only be used to compare graphs generated through different mechanisms but can reliably compare graphs of varying size. We observe that the family of Watts-Strogatz graphs lie on a manifold in the nonbacktracking spectral embedding and show how this metric can be used in a standard classification problem of empirical graphs.
Collapse
Affiliation(s)
- Andrew Mellor
- Mathematical Institute, University of Oxford, Woodstock Road, Oxford OX2 6GG, United Kingdom
| | - Angelica Grusovin
- Mathematical Institute, University of Oxford, Woodstock Road, Oxford OX2 6GG, United Kingdom
| |
Collapse
|
6
|
|
7
|
Designing Labeled Graph Classifiers by Exploiting the Rényi Entropy of the Dissimilarity Representation. ENTROPY 2017. [DOI: 10.3390/e19050216] [Citation(s) in RCA: 2] [Impact Index Per Article: 0.3] [Reference Citation Analysis] [Track Full Text] [Subscribe] [Scholar Register] [Indexed: 11/16/2022]
|
8
|
Bai L, Rossi L, Cui L, Zhang Z, Ren P, Bai X, Hancock E. Quantum kernels for unattributed graphs using discrete-time quantum walks. Pattern Recognit Lett 2017. [DOI: 10.1016/j.patrec.2016.08.019] [Citation(s) in RCA: 21] [Impact Index Per Article: 3.0] [Reference Citation Analysis] [Track Full Text] [Journal Information] [Subscribe] [Scholar Register] [Indexed: 11/30/2022]
|
9
|
Han L, Wilson RC, Hancock ER. Generative Graph Prototypes from Information Theory. IEEE TRANSACTIONS ON PATTERN ANALYSIS AND MACHINE INTELLIGENCE 2015; 37:2013-2027. [PMID: 26340255 DOI: 10.1109/tpami.2015.2400451] [Citation(s) in RCA: 3] [Impact Index Per Article: 0.3] [Reference Citation Analysis] [Abstract] [Track Full Text] [Subscribe] [Scholar Register] [Indexed: 06/05/2023]
Abstract
In this paper we present a method for constructing a generative prototype for a set of graphs by adopting a minimum description length approach. The method is posed in terms of learning a generative supergraph model from which the new samples can be obtained by an appropriate sampling mechanism. We commence by constructing a probability distribution for the occurrence of nodes and edges over the supergraph. We encode the complexity of the supergraph using an approximate Von Neumann entropy. A variant of the EM algorithm is developed to minimize the description length criterion in which the structure of the supergraph and the node correspondences between the sample graphs and the supergraph are treated as missing data. To generate new graphs, we assume that the nodes and edges of graphs arise under independent Bernoulli distributions and sample new graphs according to their node and edge occurrence probabilities. Empirical evaluations on real-world databases demonstrate the practical utility of the proposed algorithm and show the effectiveness of the generative model for the tasks of graph classification, graph clustering and generating new sample graphs.
Collapse
|
10
|
Ye C, Comin CH, Peron TKD, Silva FN, Rodrigues FA, Costa LDF, Torsello A, Hancock ER. Thermodynamic characterization of networks using graph polynomials. PHYSICAL REVIEW. E, STATISTICAL, NONLINEAR, AND SOFT MATTER PHYSICS 2015; 92:032810. [PMID: 26465531 DOI: 10.1103/physreve.92.032810] [Citation(s) in RCA: 3] [Impact Index Per Article: 0.3] [Reference Citation Analysis] [Abstract] [Track Full Text] [Subscribe] [Scholar Register] [Received: 07/22/2015] [Indexed: 06/05/2023]
Abstract
In this paper, we present a method for characterizing the evolution of time-varying complex networks by adopting a thermodynamic representation of network structure computed from a polynomial (or algebraic) characterization of graph structure. Commencing from a representation of graph structure based on a characteristic polynomial computed from the normalized Laplacian matrix, we show how the polynomial is linked to the Boltzmann partition function of a network. This allows us to compute a number of thermodynamic quantities for the network, including the average energy and entropy. Assuming that the system does not change volume, we can also compute the temperature, defined as the rate of change of entropy with energy. All three thermodynamic variables can be approximated using low-order Taylor series that can be computed using the traces of powers of the Laplacian matrix, avoiding explicit computation of the normalized Laplacian spectrum. These polynomial approximations allow a smoothed representation of the evolution of networks to be constructed in the thermodynamic space spanned by entropy, energy, and temperature. We show how these thermodynamic variables can be computed in terms of simple network characteristics, e.g., the total number of nodes and node degree statistics for nodes connected by edges. We apply the resulting thermodynamic characterization to real-world time-varying networks representing complex systems in the financial and biological domains. The study demonstrates that the method provides an efficient tool for detecting abrupt changes and characterizing different stages in network evolution.
Collapse
Affiliation(s)
- Cheng Ye
- Department of Computer Science, University of York, York, YO10 5GH, United Kingdom
| | - César H Comin
- Institute of Physics at São Carlos, University of São Paulo, PO Box 369, São Carlos, São Paulo, 13560-970, Brazil
| | - Thomas K Dm Peron
- Institute of Physics at São Carlos, University of São Paulo, PO Box 369, São Carlos, São Paulo, 13560-970, Brazil
| | - Filipi N Silva
- Institute of Physics at São Carlos, University of São Paulo, PO Box 369, São Carlos, São Paulo, 13560-970, Brazil
| | - Francisco A Rodrigues
- Institute of Mathematical and Computer Sciences, University of São Paulo, PO Box 668, São Carlos, São Paulo, 13560-970, Brazil
| | - Luciano da F Costa
- Institute of Physics at São Carlos, University of São Paulo, PO Box 369, São Carlos, São Paulo, 13560-970, Brazil
| | - Andrea Torsello
- Department of Environmental Sciences, Informatics and Statistics, Ca' Foscari University of Venice, Dorsoduro 3246-30123 Venezia, Italy
| | - Edwin R Hancock
- Department of Computer Science, University of York, York, YO10 5GH, United Kingdom
| |
Collapse
|
11
|
|
12
|
Abstract
Spectral algorithms are classic approaches to clustering and community detection in networks. However, for sparse networks the standard versions of these algorithms are suboptimal, in some cases completely failing to detect communities even when other algorithms such as belief propagation can do so. Here, we present a class of spectral algorithms based on a nonbacktracking walk on the directed edges of the graph. The spectrum of this operator is much better-behaved than that of the adjacency matrix or other commonly used matrices, maintaining a strong separation between the bulk eigenvalues and the eigenvalues relevant to community structure even in the sparse case. We show that our algorithm is optimal for graphs generated by the stochastic block model, detecting communities all of the way down to the theoretical limit. We also show the spectrum of the nonbacktracking operator for some real-world networks, illustrating its advantages over traditional spectral clustering.
Collapse
|
13
|
GIBERT JAUME, VALVENY ERNEST, BUNKE HORST. EMBEDDING OF GRAPHS WITH DISCRETE ATTRIBUTES VIA LABEL FREQUENCIES. INT J PATTERN RECOGN 2013. [DOI: 10.1142/s0218001413600021] [Citation(s) in RCA: 6] [Impact Index Per Article: 0.5] [Reference Citation Analysis] [Abstract] [Track Full Text] [Journal Information] [Subscribe] [Scholar Register] [Indexed: 11/18/2022]
Abstract
Graph-based representations of patterns are very flexible and powerful, but they are not easily processed due to the lack of learning algorithms in the domain of graphs. Embedding a graph into a vector space solves this problem since graphs are turned into feature vectors and thus all the statistical learning machinery becomes available for graph input patterns. In this work we present a new way of embedding discrete attributed graphs into vector spaces using node and edge label frequencies. The methodology is experimentally tested on graph classification problems, using patterns of different nature, and it is shown to be competitive to state-of-the-art classification algorithms for graphs, while being computationally much more efficient.
Collapse
Affiliation(s)
- JAUME GIBERT
- École Nationale Supérieure d'Ingénieurs de Caen, ENSICAEN, Université de Caen Basse-Normandie, 6 Boulevard Maréchal Juin, 14050 Caen, France
| | - ERNEST VALVENY
- Computer Vision Center, Computer Science Department, Universitat Autònoma de Barcelona, Edifici O – Campus UAB, 08193 Bellaterra, Spain
| | - HORST BUNKE
- Institute of Computer Science and Applied Mathematics, University of Bern, Neubrückstrasse 10, CH-3012 Bern, Switzerland
| |
Collapse
|
14
|
Aziz F, Wilson RC, Hancock ER. Backtrackless walks on a graph. IEEE TRANSACTIONS ON NEURAL NETWORKS AND LEARNING SYSTEMS 2013; 24:977-989. [PMID: 24808478 DOI: 10.1109/tnnls.2013.2248093] [Citation(s) in RCA: 11] [Impact Index Per Article: 1.0] [Reference Citation Analysis] [Abstract] [Track Full Text] [Subscribe] [Scholar Register] [Indexed: 06/03/2023]
Abstract
The aim of this paper is to explore the use of backtrackless walks and prime cycles for characterizing both labeled and unlabeled graphs. The reason for using backtrackless walks and prime cycles is that they avoid tottering, and can increase the discriminative power of the resulting graph representation. However, the use of such methods is limited in practice because of their computational cost. In this paper, we present efficient methods for computing graph kernels, which are based on backtrackless walks in a labeled graph and whose worst case running time is the same as that of kernels based on random walks. For clustering unlabeled graphs, we construct feature vectors using Ihara coefficients, since these coefficients are related to the frequencies of prime cycles in the graph. To efficiently compute the low order coefficients, we present an O(|V|(3)) algorithm which is better than the O(|V|(6)) worst case running time of previously known algorithms. In the experimental evaluation, we apply the proposed method to clustering both labeled and unlabeled graphs. The results show that using backtrackless walks and prime cycles instead of random walks can increase the accuracy of recognition.
Collapse
|
15
|
|
16
|
|
17
|
Gibert J, Valveny E, Bunke H. Feature selection on node statistics based embedding of graphs. Pattern Recognit Lett 2012. [DOI: 10.1016/j.patrec.2012.03.017] [Citation(s) in RCA: 3] [Impact Index Per Article: 0.3] [Reference Citation Analysis] [Track Full Text] [Journal Information] [Subscribe] [Scholar Register] [Indexed: 10/28/2022]
|
18
|
Abstract
Spectral clustering (SC) is a large family of grouping methods that partition data using eigenvectors of an affinity matrix derived from the data. Though SC methods have been successfully applied to a large number of challenging clustering scenarios, it is noteworthy that they will fail when there are significant intersections among different clusters. In this paper, based on the analysis that SC methods are able to work well when the affinity values of the points belonging to different clusters are relatively low, we propose a new method, called spectral multi-manifold clustering (SMMC), which is able to handle intersections. In our model, the data are assumed to lie on or close to multiple smooth low-dimensional manifolds, where some data manifolds are separated but some are intersecting. Then, local geometric information of the sampled data is incorporated to construct a suitable affinity matrix. Finally, spectral method is applied to this affinity matrix to group the data. Extensive experiments on synthetic as well as real datasets demonstrate the promising performance of SMMC.
Collapse
Affiliation(s)
- Yong Wang
- Department of Mathematics and Systems Science, National University of Defense Technology, Changsha, China.
| | | | | | | |
Collapse
|