key: cord-0551192-850lmbeu authors: Faccin, Mauro title: Dynamical systems on directed hyper-graphs date: 2022-02-25 journal: nan DOI: nan sha: 43186f5e72ebfd18268bf84522cafadb4e7ac697 doc_id: 551192 cord_uid: 850lmbeu Networks and graphs provide a simple but effective model to a vast set of systems which building blocks interact throughout pairwise interactions. Such models fail to describe all those systems which building blocks interact at a higher order. Higher order graphs provide us the right tools for the task. We analyze the interplay between the structure of a directed hyper-graph and a dynamical system evolving on it. We connect the dynamical system on the h to a corresponding random walk on an effective graph. Measures of hyper-dynamics correspond to similar measures on the effective dynamics. We can use simple and well tested algorithms on the effective graph. Studying complex systems often requires disaggregating those systems into simpler parts that interact with each other. Network science often name those base constituents nodes and the pairwise interaction between them edges. Unfortunately, in some cases pairwise interactions fall short to describe the initial system and one needs to follow a different route. Within the different methods introduced to tackle such problem, simplicial complexes introduce the notion of nodes that interact through simplices [1, 2] such as a segment, a triangle, a tetrahedron etc. Hyper-graphs, on the other hand, define interaction beyond pairwise through the definition of hyper-edges, edges that affect multiple nodes at once [3, 4] . When dynamical processes are coupled to the linking pattern of interacting nodes, the selection of a model to analyze the original system depends on the double choice of the topological and the dynamical models. Further, the necessity to analyze such system requires the development of new tools that extend and complete the measures developed along the years in the cases of simple pair-wise graphs and adapt them to the selected model. In this work we leverage the results on directed hypergraphs [5, 6] and recent finding characterizing dynamical systems on undirected hyper-graphs [7, 8] . We will show that, when the conditions are satisfied and the appropriate dynamics are defined on the hyper-graph, one can compute a transition matrix representing the probability to transition between any two nodes of the hyper-graph. Such transition matrix defines effective dynamics on a family of (pairwise) graphs that will microscopically reproduce the same (dynamical) behavior of the original higher-order graph, at the steady state. One may expect that measures that are function of the dynamical system, should return the same values on the hyper-graph dynamics and its pairwise effective dynamical counterpart. Finally, we describe some examples to illustrate these findings. While the selection of the topological and the dynamical models depend on each other, in the following, for simplicity, we describe them independently. A h G h = {N, E} is defined by a set of nodes N that interact through a set of hyper-edges E. A hyper-edge e ∈ E represents the interaction between two or more nodes, the interaction can be directed. When the hypergraph is directed, the nodes involved in the interaction are divided in two (possibly overlapping) subsets: the source of the interaction called tail of the hyper-edge; and the target of the interaction called head (see Figure 1 ). The nomenclature, tail and head, represents the directionality of the interaction through the figure of the arrow. This construction is reminiscent of the chemical reaction hyper-graphs [9] where incoming and outgoing interactions are defined by positive and negative values. Hyper-edge weights can be introduced as a weighting factor w α . In some cases, as in the following, it may be useful to define hyper-edges weights as functions of the corresponding hyper-edge characteristics (such as the number of nodes involved). We can introduce an interaction matrix I. where W = diag(w) is the square weight matrix with hyper-edge weights on the diagonal. a. Forward hyper-edges In the following we can suppose that all hyper-edges have tails of size one, the socalled forward hyper-edges. Otherwise, hyper-edges with larger tails can decompose to a set of forward hyper-edges each with the tail on a node of the former hyper-edge and the same head. In this framework, all columns of the tail matrix T have exactly one non-zero element ( i T iα = 1 ∀α). We will refer to the size of the hyper-edge (|e|) as the number of nodes included into its head: |e α | = i H iα . When all the hyper-edges have size one (|e α | = 1 ∀α), the hyper-graph reduces to a normal graph with pair-wise interactions. A hyper-graph is symmetric when for any hyper-edge e α , there exists other |e α | hyper-edges with tail on each of its head nodes and head on the other involved nodes. b. Hyper-edge weights as function of the size. It may be useful to define the weight on the hyper-edge as a function of the hyper-edge size, in particular: where τ is a biasing parameter. For positive values of the latter, hyper-edges with large heads have higher weights, and vice versa for negative values. A dynamical system that leverage the hyper-graph connectivity can be defined in a number of ways. In the following we describe a family of linear dynamics on a hyper-graph, as defined in [10] for the symmetric case. A dynamical system linked to the hyper-graph can be interpreted as a special case of the (hyper) graph signal processing [4] , where the signal vector is constrained to be normalized and the shift operator is a right stochastic matrix. Consider, in this case, a dynamical system evolving on a directed hyper-graph G h , as a generalization of the classical random walk on a simple graph. At each time step the walker, sitting on node i, will perform the following steps: 1. choose a neighboring hyper-edge which tail include node i with a probability proportional to the hyperedge weight, 2. traverse the hyper-edge to one of the nodes of its head, Hence, the biasing parameter τ will influence the dynamics warping the walker toward hyper-edges with larger or smaller heads. In particular, with τ = −1 the dynamics will select each tail with equal probability [3] while with τ = 0 they will select each tail with probability proportional to the respective hyper-edge size. The transition probability between two nodes i and j can be written as (with a simple normalization): where τ is a bias parameter, and I the interaction matrix of Eq. 1, with the hyper-edge weights as in Eq.2. The probabilities in Eq.3 determine the entries of the right stochastic transition matrix T ij (τ ) = p τ (j|i). In particular: where 1 is the vector of all ones. Assuming ergodic dynamics, one can compute a steady state π τ which encodes the probability of the walker to visit a given node of the hyper-graph. The steady state π τ is the dominant eigenvector of the transition matrix T (τ ) that corresponds to its unit eigenvalue. The probability of leaving node i and reaching node j at the following time step is p τ (i, j) = π τ i p τ (j|i). This defines the probability matrix: a. The effective graph. At this point, an interesting question is: can we find an effective graph which, coupled with a random walk, will microscopically reproduce the dynamical behavior of the original system? The answer to this requires a distinction. In the simpler case of a symmetric hyper-graph, one would expect a symmetric effective graph, this implies that the corresponding adjacency matrix would be proportional to the probability matrix of Eq.5. In particular the interaction matrix I(τ ) is in this case a suitable representative of all possible effective adjacency matrices, which can all be written as A(τ ) = αI(τ ) = α I(τ ) Π τ (with α a positive multiplicative factor and · the L 1,1 norm). Unfortunately, this is not the case in for a directed hyper-graph. There exists, in fact, a (infinite) family of graphs that correspond to a given transition matrix. Since we cannot assume the symmetry of any effective graph and the out-degree sequence cannot be imposed, any matrix of the form A = diag( v)T (τ ) is a suitable adjacency matrix. In particular, in this case, the interaction matrix I(τ ) and the probability matrix Π τ together with the transition matrix itself, are only few representatives of that family. b. The clique expansion. Often, in the literature, one can find approaches involving the clique expansion of (symmetric) hyper-graphs. Here, a hyper-edge is replaced by a clique of (pairwise) links between all the nodes involved in the original higher order interaction. This approach assumes that the dynamics can freely flow between any pair of nodes involved in the interaction. Considering the analysis conducted so far, for a symmetric hyper-graph, clique expansion use the interaction matrix of Eq.1 as adjacency matrix of the effective graph, fixing τ = 0. This choice is assuming, thus, a precise (linear) dynamical model, in particular with τ = 0, where a random walker will choose neighboring hyper-edges according (proportionally) to their head size. One may expect that measures that are mere function of the dynamical system return the same result when applied to a dynamical system on a hyper-graphs or to a pairwise graph, when those display the same dynamical behavior. Measures of the transition matrix T (τ ) (Eq. 3) or the probability matrix Π τ (Eq. 5) that characterize the dynamical system will depend on the value of the biasing parameter τ . However, those measures involve pair-wise matrices and provide a basis for a straightforward extension of similar measures on simple graphs. For a simple graph, the eigenvector centrality x i of node i represents its connection degree to other highly ranked nodes. The eigenvector equation computes the centrality vector in vector notation: where λ 0 is the largest eigenvalue of the adjacency matrix A. In the hyper-graph case, we have no access to the adjacency matrix, but a good candidate for that role is the probability matrix of Eq. 5: In Figure 2 we present a didactic example of a hypergraph of 5 nodes and 6 hyper-edges. In this graph, hyperedges of size one point to node 0, while hyper-edges of size 3 point mostly to node 1. Note how the ranking of nodes according to the eigencentrality defined as in Nodes of the graph in Figure 2 are sorted according to the Pagerank. As for the eigencentrality case of Figure 2 , the relative ordering of nodes can be changes modifying the value of the bias parameter τ . Eq. 7 depends on the value of the bias parameter τ . For negative values of τ the dynamics follow preferentially small edges, hence node 0 has the highest rank. For positive values of τ the highest ranked node is node 1. Pagerank [11] is a similar node ranking algorithm designed to rank web-pages according to the user visiting behavior. The algorithm models the browsing behavior of the user as a random walk with teleportation and the ranking value corresponds to the visiting probability of each node π τ i (the dominant right eigenvector of the transfer matrix, comprising the teleportation term). Extending the pagerank to the hyper-graph framework is straightforward as merely a function of the transfer matrix. Table I shows the ranking of the hyper-graph nodes as in the hyper-graph of Figure 2 . Notice a ranking reordering similar to that from eigencentrality when the bias parameter τ changes its value. Tran et al, in [6] , use a similar approach fixing the bias parameter τ = −1. However, they use a symmetrized version of the Laplacian instead of computing the dominant eigenvector from the transition matrix. Tudisco et al. [12] introduce a different approach to calculate the eigencentrality of a hyper-graph inspired by the HITS algorithm. Here, the importance of nodes and edges depends on the importance of the neighboring edges and nodes respectively (as opposed to using hub and authority centralities for nodes only). The simple linear case translates, for the node ranking, to finding the dominant right eigenvector of the interaction matrix: Unfortunately the interaction matrix is not always a function of the dynamics. However, if the interaction matrix is symmetric, as for the simple graph, the steady state assumes the simple form (we omit the dependence on τ ): where · represents the L 1,1 norm or the sum of all entries. In fact, one can see that the Eq. 9 defines a stationary state: The elements of the interaction matrix are then proportional to the probability matrix Π(τ ): and then can be derived by the dynamics except for a multiplicative factor I −1 . Extending community detection algorithms that involve a measure of the dynamics is also at reach. Consider modularity [13] which is the objective function of a number of algorithms [14, 15] . In this framework the algorithm tries to maximize the modularity function which, in a symmetric graph, is: where A is the adjacency matrix, k i = j A ij is the node degree (or strength in the weighted case), m = 1 2 ij A ij is the number of edges and c i is the community assigned to node i. While the Eq. 12 is a function of the linking pattern, it has been shown that it can be rewritten as a sum of auto-covariance of a random walk [16, 17] : providing a dynamical interpretation of modularity maximization. In a symmetric graph, the above equation translates to: that depends only on Π τ . The above relation between modularity and autocovariance maximization holds for the symmetric case where the probability matrix Π is proportional to the adjacency matrix of the graph and the steady state probability distribution is proportional to the node degrees. Leicht and Newman extend the modularity function to directed networks [18] disentangling the modularity definition from its dynamical interpretation. Inspired by the relation between covariance and modularity, Delvenne et al [16] provide an extension of Eq. III B to directed graphs and to different time scales. This formulation, which utilizes the dynamical system to cluster the graph nodes, let us extend the community detection algorithm to hyper-graphs [7] . An online social network like Twitter, where the discussion follows a one-to-many pattern, represents a system where hyper-graphs are best suited. Figure 3 shows the community structure of users on the French-speaking part of Twitter, discussing vaccine related topics in the context of the COVID-19 pandemic (dataset from [19] ). Each tweeting user represents the tail of a hyper-edge whose head nodes are the retweeting users, and communities are detected through the maximization of the auto-covariance. Here we plot for different values of τ the average visiting probability (the probability of visiting a node of a given partition, on average) and the escape probability (the probability of reaching a node on a different community) of each community. When comparing the communities computed with τ = −1 (each tweet has the same weight) or τ = 0 (each tweet weight is proportional to the number of its retweets) one can notice that the in the upper part of the plots (the most prolific communities), there is a shift toward higher outgoing flows. The dynamics corresponding to higher values of τ favors, for those communities, hyper-edges with larger heads (higher number of retweets). The shift in Figure 3 uncover a higher probability of tweets/hyper-edges with larger cascades/heads to reach other communities. Figure 4 shows the escape probability of the larger communities. Notice that the probability of reaching nodes on different communities is an increasing function of τ in the range of values analyzed. The communities are recomputed independently at each value of τ and the same name is assigned if they overlap more than 90%. This account for some of the fluctuations due to merging and splitting of communities. We analyze the capacity of tweets of different cascade size to reach a different community of the original poster. this work. Some notable examples could be the mapequation [20] which was extended to symmetric hypergraphs in [7] . Another algorithm based on information theoretical arguments amenable to extension is the autoinformation state aggregation [21] . We discussed how the analysis of higher order graphs can be performed through the analysis of the dynamical system coupled to the hyper-edge topology. When a transition matrix can be computed for the steady state of the dynamics, all measures that are function of the latter can be applied directly. One can assume that a function of the dynamics have the same results if dynamics on a hyper-graph and on the corresponding graph with identical transition matrix. Prudence is necessary. Although an effective transition matrix may exist in some cases, to such transition matrix correspond a whole family of possible adjacency matrices which produce the same transition probabilities. While in the symmetric case one can naïvely analyze the interaction matrix of Eq.1 as an adjacency matrix of an effective graph, this can lead to misconceptions. In particular one may be tempted to analyze the linking pattern of such effective graph incurring into an improper extension of the measure of interest. In the directed case, the analysis of the interaction matrix does not directly relate to the dynamical behavior of the original system. Other popular approaches involve an expansion of the hyper-edge pattern, e.g. clique expansion which assumes a specific dynamical model that may not match the original system. If the interest of the researcher is instead on the linking pattern of the hyper-graph, one must redefine the measure of interest, as in [12, 22] where the authors define a new eigencentrality or clustering coefficient adapted to this framework. A topic of interest for further studies would be how to determine the dynamical model to use on the hyper-graph structure, in particular, in the linear case, the best value of τ . In many cases, as in the preset work, the choice fall on the researcher, and they need to determine the value of τ or to analyze a range of values. Another way would be to use one of the many model selection approaches applied to the measure of interest, such as the elbow or the plateau criterions. Another topic of interest for further studies is determining when this framework is applicable to non-linear dynamics such non-Markovian [23] dynamics or quantum mechanical systems [24, 25] . In the former the dynamics depends on the symbols visited in the past (the dynamics is linear on the set of present and past symbols). In the latter the quantum system evolves on the nodes, and, while there is no steady state, one may consider temporal averages or open quantum systems (coupled with a bath). Generalized network structures: The configuration model and the canonical ensemble of simplicial complexes Simplicial activity driven model Learning with hypergraphs: Clustering, classification, and embedding Signal processing on higher-order networks: Livin Directed hypergraphs and applications Pagerank algorithm for directed hypergraph Random walks and community detection in hypergraphs Flow-based community detection in hypergraphs Spectral theory of Laplace operators on oriented hypergraphs Random walks on hypergraphs The anatomy of a large-scale hypertextual web search engine Node and edge nonlinear eigenvector centrality for hypergraphs Finding and evaluating community structure in networks Fast unfolding of communities in large networks From louvain to leiden: Guaranteeing well-connected communities Stability of graph communities across time scales Multiscale dynamical embeddings of complex networks Community structure in directed networks Assessing the influence of french vaccine critics during the two first years of the COVID-19 pandemic The map equation State aggregations in Markov chains and block models of networks Subgraph centrality and clustering in complex hyper-networks Using higher-order markov models to reveal flowbased communities in networks Complex networks from classical to quantum Quantum hypergraph states MF thanks Michael Schaub for the insightful discussions on the topic. Part of this work has benefited from the financial support of the Agence Nationale de la Recherche (projects TRACTRUST -ANR-20-COVI-0102).