Source author record

Dario Fasino

Dario Fasino appears in the imported research catalog. Authorship, coauthor and topic links are available while profile ownership is still unclaimed.

ResearcherUnclaimed source record

math.NA Social and Information Networks math.SP physics.soc-ph math.DS math.PR Numerical Analysis

Catalog footprint

What is connected

6works

7topics

2close collaborators

Actions

Connect this record

Open graph Browse works

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

preprint2021arXiv

Generating large scale-free networks with the Chung-Lu random graph model

Random graph models are a recurring tool-of-the-trade for studying network structural properties and benchmarking community detection and other network algorithms. Moreover, they serve as test-bed generators for studying diffusion and routing processes on networks. In this paper, we illustrate how to generate large random graphs having a power-law degree distribution using the Chung--Lu model. In particular, we are concerned with the fulfilment of a fundamental hypothesis that must be placed on the model parameters, without which the generated graphs lose all the theoretical properties of the model, notably, the controllability of the expected node degrees and the absence of correlations between the degrees of two nodes joined by an edge. We provide explicit formulas for the model parameters to generate random graphs that have several desirable properties, including a power-law degree distribution with any exponent larger than $2$, a prescribed asymptotic behaviour of the largest and average expected degrees, and the presence of a giant component.

preprint2020arXiv

Ergodicity coefficients for higher-order stochastic processes

The use of higher-order stochastic processes such as nonlinear Markov chains or vertex-reinforced random walks is significantly growing in recent years as they are much better at modeling high dimensional data and nonlinear dynamics in numerous application settings. In many cases of practical interest, these processes are identified with a stochastic tensor and their stationary distribution is a tensor $Z$-eigenvector. However, fundamental questions such as the convergence of the process towards a limiting distribution and the uniqueness of such a limit are still not well understood and are the subject of rich recent literature. Ergodicity coefficients for stochastic matrices provide a valuable and widely used tool to analyze the long-term behavior of standard, first-order, Markov processes. In this work, we extend an important class of ergodicity coefficients to the setting of stochastic tensors. We show that the proposed higher-order ergodicity coefficients provide new explicit formulas that (a) guarantee the uniqueness of Perron $Z$-eigenvectors of stochastic tensors, (b) provide bounds on the sensitivity of such eigenvectors with respect to changes in the tensor and (c) ensure the convergence of different types of higher-order stochastic processes governed by cubical stochastic tensors. Moreover, we illustrate the advantages of the proposed ergodicity coefficients on several example application settings, including the analysis of PageRank vectors for triangle-based random walks and the convergence of lazy higher-order random walks.

preprint2016arXiv

Localization of dominant eigenpairs and planted communities by means of Frobenius inner products

We propose a new localization result for the leading eigenvalue and eigenvector of a symmetric matrix $A$. The result exploits the Frobenius inner product between $A$ and a given rank-one landmark matrix $X$. Different choices for $X$ may be used, depending upon the problem under investigation. In particular, we show that the choice where $X$ is the all-ones matrix allows to estimate the signature of the leading eigenvector of $A$, generalizing previous results on Perron-Frobenius properties of matrices with some negative entries. As another application we consider the problem of community detection in graphs and networks. The problem is solved by means of modularity-based spectral techniques, following the ideas pioneered by Miroslav Fiedler in mid 70s. We show that a suitable choice of $X$ can be used to provide new quality guarantees of those techniques, when the network follows a stochastic block model.

preprint2016arXiv

Modularity bounds for clusters located by leading eigenvectors of the normalized modularity matrix

Nodal theorems for generalized modularity matrices ensure that the cluster located by the positive entries of the leading eigenvector of various modularity matrices induces a connected subgraph. In this paper we obtain lower bounds for the modularity of that set of nodes showing that, under certain conditions, the nodal domains induced by eigenvectors corresponding to highly positive eigenvalues of the normalized modularity matrix have indeed positive modularity, that is they can be recognized as modules inside the network. Moreover we establish Cheeger-type inequalities for the cut-modularity of the graph, providing a theoretical support to the common understanding that highly positive eigenvalues of modularity matrices are related with the possibility of subdividing a network into communities.

preprint2015arXiv

Generalized modularity matrices

Various modularity matrices appeared in the recent literature on network analysis and algebraic graph theory. Their purpose is to allow writing as quadratic forms certain combinatorial functions appearing in the framework of graph clustering problems. In this paper we put in evidence certain common traits of various modularity matrices and shed light on their spectral properties that are at the basis of various theoretical results and practical spectral-type algorithms for community detection.

preprint2014arXiv

An algebraic analysis of the graph modularity

One of the most relevant tasks in network analysis is the detection of community structures, or clustering. Most popular techniques for community detection are based on the maximization of a quality function called modularity, which in turn is based upon particular quadratic forms associated to a real symmetric modularity matrix $M$, defined in terms of the adjacency matrix and a rank one null model matrix. That matrix could be posed inside the set of relevant matrices involved in graph theory, alongside adjacency, incidence and Laplacian matrices. This is the reason we propose a graph analysis based on the algebraic and spectral properties of such matrix. In particular, we propose a nodal domain theorem for the eigenvectors of $M$; we point out several relations occurring between graph's communities and nonnegative eigenvalues of $M$; and we derive a Cheeger-type inequality for the graph optimal modularity.