Paper accepted on SIAM Applied Mathematics
Our paper Total variation based community detection using a nonlinear optimization approach, joint work with Andrea Cristofari and Francesco Rinaldi from the University of Padua, has been accepted on the SIAM Journal on Applied Mathematics
Visit and Talk @ Uni Kent
I am traveling today to visit and give a talk at the pure, applicable and numerical mathematics seminar at University of Kent, Canterbury (UK). Thanks Bas Lemmens and Marina Iliopoulou for the invitation and for hosting me!
New paper out
Convergence of the nonlinear power method for matrix norms with application to the log-Sobolev constant of Markov chains
Abstract: We analyze the global convergence of the power iterates for the computation of a general mixed-subordinate matrix norm. We prove a new global convergence theorem for a class of entrywise nonnegative matrices that generalizes and improves a well-known results for mixed-subordinate $\ell^p$ matrix norms. In particular, exploiting the Birkoff–Hopf contraction ratio of nonnegative matrices, we obtain novel and explicit global convergence guarantees for a range of matrix norms whose computation has been recently proven to be NP-hard in the general case, including the case of mixed-subordinate norms induced by the vector norms made by the sum of different $\ell^p$-norms of subsets of entries. ... Read more
Seminar talk @ RAL
I am in Oxford (UK) today, giving a talk at the Rutherford Appleton Lab and Uni of Oxford’s Numerical Analysis group joint seminar on Computational Mathematics and Applications. Thank you Michael Wathen and Tyrone Rees for the invitation!
Paper accepted on Proc Royal Society A
Our paper A framework for second order eigenvector centralities and clustering coefficients, joint work with Francesca Arrigo and Des Higham, has been accepted in the Proceedings of the Royal Society Series A
Doctoral course @ Uni Padua
Starting from March 1, I will be visiting the University of Padua to teach the doctoral course Eigenvector methods for learning from data on networks for the PhD program in Computational Mathematics. You can use this link if you wish to enroll for my course. Thanks Michela for the invitation!
Plenary talk @ HHXXI
I have been invited to give a plenary talk this summer at the Householder Symposium XXI. You can read the abstract of my talk from the book of abstracts. Looking forward for this exciting opportunity!
New paper out
Nonlocal PageRank
Abstract: In this work we introduce and study a nonlocal version of the PageRank. In our approach, the random walker explores the graph using longer excursions than just moving between neighboring nodes. As a result, the corresponding ranking of the nodes, which takes into account a long-range interaction between them, does not exhibit concentration phenomena typical for spectral rankings taking into account just local interactions. We show that the predictive value of the rankings obtained using our proposals is considerably improved on different real world problems. ... Read more
Konstantin successfully passed today his preliminary PhD exam. Congratulations!
Our paper Generalized Matrix Means for Semi-Supervised Learning with Multilayer Graphs is being presented today by Pedro Mercado at NeurIPS 2019. You may wish to have a look at the poster:
SIAM Workshop on Network Science 2020
Excited to be part of the Program Committee of the SIAM Workshop on Network Science!
We invite contributions focused on all aspects of mathematical, algorithmic, data analysis, and computational techniques in network science and its applications. Accepted submissions will be featured in the workshop as a 20-minute talk, 5-minute talk, or poster.
Submission deadline: February 20, 2020
Twitter feed: #SIAMNS20
The workshop is co-located with the Second Joint SIAM/CAIMS Annual Meeting, the SIAM Conference on Imaging Science (IS20), and the Canadian Symposium on Fluid Dynamics.
Rome-Moscow school 2020
The 7th edition of the Rome Moscow summer school on Matrix Methods and Applied Linear Algebra is in preparation! This is the 10th anniversary of this exciting series of summer schools. The tentative dates for the school are:
- Moscow: Aug 22 – Sept 5
- Rome: Sept 6 – Sept 20
The school is meant for both final years undergraduate and graduate students who are intrigued by Applied Mathematics and Matrix Methods. The summer school takes place over the course of one entire month—in the two beautiful cities of Rome (Italy) and Moscow (Russia)—and thus it allows the students to really work over the topics that are discussed. Also it is a wonderful occasion to meet new people in the field of Applied Linear Algebra. I have been student of several editions of the school and strongly encourage participation. Please, feel free to contact me if you have questions.
New paper out
Generalized matrix means for semisupervised learning with multilayer graphs
Abstract: We study the task of semi-supervised learning on multilayer graphs by taking into account both labeled and unlabeled observations together with the information encoded by each individual graph layer. We propose a regularizer based on the generalized matrix mean, which is a one-parameter family of matrix means that includes the arithmetic, geometric and harmonic means as particular cases. We analyze it in expectation under a Multilayer Stochastic Block Model and verify numerically that it outperforms state of the art methods. ... Read more
--- Poster that will be presented at NeurIPS19, by Pedro Mercado
New paper out
A framework for second order eigenvector centralities and clustering coefficients
Abstract: We propose and analyse a general tensor-based framework for incorporating second order features into network measures. This approach allows us to combine traditional pairwise links with information that records whether triples of nodes are involved in wedges or triangles. Our treatment covers classical spectral methods and recently proposed cases from the literature, but we also identify many interesting extensions. In particular, we define a mutually-reinforcing (spectral) version of the classical clustering coefficient. ... Read more
--- Nodes with largest spectral clustering coefficient in the karate club network, for different tensors.
New paper out
Generating large scale-free networks with the Chung-Lu random graph model
Abstract: Being able to produce synthetic networks by means of generative random graph models and scalable algorithms is a recurring tool-of-the-trade in network analysis, as it provides a well founded basis for the statistical analysis of various properties in real-world networks. In this paper, we illustrate how to generate large random graphs having a power-law degree profile by means of the Chung-Lu model. In particular, we are concerned with the fulfillment of a fundamental hypothesis that must be placed on the model parameters, without which the generated graphs loose 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. ... Read more
--- The power law degree distribution of random graphs in the Chung-Lu model.
New paper out
Shifted and extrapolated power methods for tensor $\ell^p$-eigenpairs
Abstract: This work is concerned with the computation of $\ell^p$-eigenvalues and eigenvectors of square tensors with $d$ modes. In the first part we propose two possible shifted variants of the popular (higher-order) power method for the computation of $\ell^p$-eigenpairs proving the convergence of both the schemes to the Perron $\ell^p$-eigenvector of the tensor, and the maximal corresponding $\ell^p$-eigenvalue, when the tensor is entrywise nonnegative and $p$ is strictly larger than the number of modes. ... Read more
Paper accepted on NeurIPS19
I am delighted to hear that our paper Generalized Matrix Means for Semi-Supervised Learning with Multilayer Graphs – with Pedro Mercado and Matthias Hein – got accepted on the proceedings of this year’s NeurIPS conference.
New paper out
A fast and robust kernel optimization method for core–periphery detection in directed and weighted graphs
Abstract: Many graph mining tasks can be viewed as classification problems on high dimensional data. Within this class we consider the issue of discovering core-periphery structure, which has wide applications in the economic and social sciences. In contrast to many current approaches, we allow for weighted and directed edges and we do not assume that the overall network is connected. Our approach extends recent work on a relevant relaxed nonlinear optimization problem. ... Read more
--- Edge probability $p_{ij}(u)$ in the logistic core-periphery random graph model.
New paper out
Total variation based community detection using a nonlinear optimization approach
Abstract: Maximizing the modularity of a network is a successful tool to identify an important community of nodes. However, this combinatorial optimization problem is known to be NP-hard. Inspired by recent nonlinear modularity eigenvector approaches, we introduce the modularity total variation $TV_Q$ and show that its box-constrained global maximum coincides with the maximum of the original discrete modularity function. Thus we describe a new nonlinear optimization approach to solve the equivalent problem leading to a community detection strategy based on $TV_Q$. ... Read more
New paper out
Ergodicity coefficients for higher-order stochastic processes
Abstract: Ergodicity coefficients for stochastic matrices provide valuable upper bounds for the magnitude of subdominant eigenvalues, allow to bound the convergence rate of methods for computing the stationary distribution and can be used to estimate the sensitivity of the stationary distribution to changes in the matrix. In this work we extend an important class of ergodicity coefficients defined in terms of the 1-norm 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 -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 power methods to the stationary distribution of higher-order and vertex-reinforced Markov chains. ... Read more
Visiting City University of Hong Kong
This week (July 1 - July 5) I am in Kowloon, HK, visiting the Department of Mathematics and the School of Data Science of the City University of Hong Kong.
Exciting Strathclyde conferences coming soon: NACONF19 & EUROPT19
The University of Strathclyde is hosting two major conferences this summer:
The 28th Biennial Numerical Analysis Conference (see also my previous post), where I will give the talk Networks core-periphery detection with nonlinear Perron eigenvectors and the 17th Workshop on Advances in Continuous Optimization, where I will give the talk Leading community detection in networks via total variation optimization.
Looking forward to both events!
New paper out
Extrapolation methods for fixed-point multilinear PageRank computations
Abstract: Nonnegative tensors arise very naturally in many applications that involve large and complex data flows. Due to the relatively small requirement in terms of memory storage and number of operations per step, the (shifted) higher-order power method is one of the most commonly used technique for the computation of positive Z-eigenvectors of this type of tensors. However, unlike the matrix case, the method may fail to converge even for irreducible tensors. ... Read more
Biennial Numerical Analysis Conference
Looking forward for the 28th Biennial Numerical Analysis Conference, admirably organized by my friends and colleagues Alison Ramage, Phil Knight, John Mackenzie from the Math&Stats department at Strathclyde. Have a look at the exciting program and let’s not forget to tweet! #NACONF19
I am organizing a minisymposium and giving a talk:
Minisymposium: Matrix methods for networks
jointly organized with Francesca Arrigo
Abstract: There is a strong relationship between network science and linear algebra, as complex networks can be represented and manipulated using matrices. Some popular tasks in network science, such as ranking nodes, identifying hidden structures, or classifying and labelling components in networks, can be tackled by exploiting the matrix representation of the data. In this minisymposium we sample some recent contributions that build on an algebraic representation of standard and higher-order networks to design models and algorithms to address a diverse range of network problems, including (but not limited to) core-periphery detection and centrality.
Speakers:
- Francesca Arrigo (Strathclyde)
- Mihai Cucuringu (Oxford)
- Gissell Estrada-Rodriguez (Heriot-Watt)
- Dario Fasino (Udine)
- Philip Knight (Strathclyde)
- Francesco Tudisco (Strathclyde)
My talk will be on Networks core-periphery detection with nonlinear Perron eigenvectors
This event is part of the research project MAGNET for which I would like to acknowledge support from the Marie Curie individual fellowship scheme.
New paper out
Spectral Clustering of Signed Graphs via Matrix Power Means
Abstract: Signed graphs encode positive (attractive) and negative (repulsive) relations between nodes. We extend spectral clustering to signed graphs via the one-parameter family of Signed Power Mean Laplacians, defined as the matrix power mean of normalized standard and signless Laplacians of positive and negative edges. We provide a thorough analysis of the proposed approach in the setting of a general Stochastic Block Model that includes models such as the Labeled Stochastic Block Model and the Censored Block Model. ... Read more
--- SBM spectral embeddings for different power mean Laplacians
New paper out
Multi-Dimensional, Multilayer, Nonlinear and Dynamic HITS
Abstract: We introduce a ranking model for temporal multi-dimensional weighted and directed networks based on the Perron eigenvector of a multi-homogeneous order-preserving map. The model extends to the temporal multilayer setting the HITS algorithm and defines five centrality vectors: two for the nodes, two for the layers, and one for the temporal stamps. Nonlinearity is introduced in the standard HITS model in order to guarantee existence and uniqueness of these centrality vectors for any network, without any requirement on its connectivity structure. ... Read more
ICIAM19: International Congress on Industrial and Applied Mathematics
I am organizing a 16 speakers (super-)minisymposium and giving a talk at the next ICIAM19 conference in Valencia (Spain), July 15-19.
Minisymposium: Mining and Modeling Evolving and Higher-Order Complex Data and Networks
jointly organized with Austin Benson, Christine Klymko, Eisha Nathan.
Abstract: The analysis of complex networks is a rapidly growing field with applications in many diverse areas. A typical computational paradigm is to reduce the system to a set of pairwise relationships modeled by a graph (matrix) and employ tools within this framework. However, many real-world networks feature temporally evolving structures and higher-order interactions. Such components are often missed when using static and lower-order methods. This minisymposium explores recent advances in models, theory, and algorithms for dynamic and higher-order interactions and data, spanning a broad range of topics including persistent homology, tensor analysis, random walks with memory, and higher-order network analysis.
Group1 – Community detection and clustering
- Christine Klymko, LLNL
Improving seed set expansion with semi-supervised information - Tim La Fond, LLNL
Representing the Evolution of Communities in Dynamic Networks - Nate Veldt, Purdue
Algorithmic Advances in Higher-Order Correlation Clustering - Marya Bazzi, ATI
Community structure in temporal multilayer networks
Group2 – Simplicial complexes
- Heather Harrington, Oxford
Topological data analysis for investigation of dynamics and biological networks - Alice Patania, Indiana
Null hypothesis for simplicial complexes - Braxton Osting, Utah
Spectral Sparsification of Simplicial Complexes for Clustering and Label Propagation - Austin Benson, Cornell
Simplicial closure and higher-order link prediction.
Group3 – Tensor methods and high-performance computing
- Francesca Arrigo
Eigenvector-based Centrality Measures in Multilayer Networks - Orly Alter, Utah
Multi-Tensor Decompositions for Personalized Cancer Diagnostics, Prognostics, and Therapeutics. - Chunxing Yin, GA Tech
A New Algorithm Model for Massive-Scale Streaming Graph Analysis - Tahsin Reza, UBC
Distributed Algorithms for Exact and Fuzzy Graph Pattern Matching
Group4 – Higher-order random walks
- Eisha Nathan, LLNL
Nonbacktracking Walks in Dynamic Graphs - Michael Schaub, MIT
Random walks on simplicial complexes and the normalized Hodge Laplacian - Keita Iwabuchi, LLNL
- Francesco Tudisco, Strathclyde
Higher-order ergodicity coefficients
This event is part of the research project MAGNET for which I would like to acknowledge support from the Marie Curie individual fellowship scheme.
New paper out
A nonlinear spectral method for core-periphery detection in networks
Abstract: We derive and analyse a new iterative algorithm for detecting network core–periphery structure. Using techniques in nonlinear Perron-Frobenius theory, we prove global convergence to the unique solution of a relaxed version of a natural discrete optimization problem. On sparse networks, the cost of each iteration scales linearly with the number of nodes, making the algorithm feasible for large-scale problems. We give an alternative interpretation of the algorithm from the perspective of maximum likelihood reordering of a new logistic core–periphery ... Read more
--- Top ten core train stations in the city of London
ALAMA NLA 2019
I have accepted the kind invitation of José Mas and Fernando de Terán Vergara to give a two-hour lecture in June (17-19) at the ALAMA (Spanish Society for Linear Agebra, Matrix Analysis and Applications) 2019 workshop at the Polytechnic University of Valencia.
Brief lecture course at Rome-Moscow school 2018
I will be visiting the Department of Mathematics of University of Rome “Tor Vergata”, my alma mater, from Monday September 17 to Friday 21 and in occasion of the Rome-Moscow school on Matrix Methods and Applied Linear Algebra. See also my previous post. I will teach a brief course on nonlinear spectral methods for higher-order centrality and core-periphery detection in networks. I hope to finish my notes and the associated Julia Notebooks soon, and post them here. A quick look to the weather forecast: today the temperature in Rome is more than twice (30C) the one here in Scotland (14C).
New paper out
The contractivity of cone-preserving multilinear mappings
Abstract: With the notion of mode-$j$ Birkhoff contraction ratio, we prove a multilinear version of the Birkhoff-Hopf and the Perron-Fronenius theorems, which provide conditions on the existence and uniqueness of a solution to a large family of systems of nonlinear equations of the type $$f_i(x_1,…,x_ν)= λ_i x_i, ,$$ being $x_i$ and element of a cone $C_i$ in a Banach space $V_i$. We then consider a family of nonlinear integral operators $f_i$ with positive kernel, acting on product of spaces of continuous real valued functions. ... Read more
Visiting KTH Royal Institute of Technology
I look forward to visit and give a seminar talk at the Numerical Analysis group of the Department of Mathematics of KTH in Stockholm, Sweden. I will stay there for two weeks: Sunday August 26 to Saturday September 8. Thanks Elias for the kind invitation and for hosting me!
Two conferences in June
I am participating at two exciting conferences next June 2018:
-
SIAM Imaging Science Conference in Bologna, from June 5 to June 8, and
-
IMA Numerical Linear Algebra and Optimization Conference in Birmingham, from June 27 to June 29.
The program of both events looks very exciting, I am really looking forward for them.
At SIAM IS I will present my work on Community detection with nonlinear modularity (based on this paper) at the minisymposium Optimization for Imaging and Big Data (see here) organized by Francesco Rinaldi and Margherita Porcelli.
At IMA NLA OPT I will present my work on Small updates of function of adjacency matrices (based on this paper) at the minisymposium Matrix Functions and Quadrature Rules with Applications to Complex Network (see here) organized by Francesca Arrigo and Stefano Pozza.
SIAM Applied Linear Algebra 2018
I am flying to Hong Kong today to attend the SIAM Applied Linear Algebra conference 2018 where I am organizing a minisymposium on Nonlinear Perron-Frobenius theory and applications and giving a talk titled A new Perron-Frobenius theorem for nonnegative tensors. See also my previous post.
New paper out
The Power Mean Laplacian for Multilayer Graph Clustering
Abstract: Multilayer graphs encode different kind of interactions between the same set of entities. When one wants to cluster such a multilayer graph, the natural question arises how one should merge the information form different layers. We introduce in this paper a one-parameter family of matrix power means for merging the Laplacians from different layers and analyze it in the stochastic block model. We show that this family allows to recover ground truth clusters under different settings and verify this in real world data. ... Read more
New paper out
The expected adjacency and modularity matrices in the degree corrected stochastic block model
Abstract: We provide explicit expressions for the eigenvalues and eigenvectors of matrices that can be written as the Hadamard product of a block partitioned matrix with constant blocks and a rank one matrix. Such matrices arise as the expected adjacency or modularity matrices in certain random graph models that are widely used as benchmarks for community detection algorithms. Please cite this work as: @article{fasino2018expected, title={The expected adjacency and modularity matrices in the degree corrected stochastic block model}, author={Fasino, Dario and Tudisco, Francesco}, journal={Special Matrices}, volume={6}, pages={110--121}, year={2018} }
Visiting University of Padua
I will be visiting the Department of Mathematics of University of Padua from Monday 5 to Friday 9 February. Very excited to meet some of my past colleagues and to have the chance to work over various ongoing collaborations. Moreover, the Italian workshop “Due Giorni” on Numerical Linear Algebra will take place in the Department on Thursday 8 and Friday 9. According to the list of participants and their abstracts a lot of interesting work will be presented. I will give a talk on Multi-dimensional nonlinear Perron-Frobenius theorem and its application to network centrality. Here is my abstract.
New paper out
A unifying Perron-Frobenius theorem for nonnegative tensors via multihomogeneous maps
Abstract: We introduce the concept of shape partition of a tensor and formulate a general tensor eigenvalue problem that includes all previously studied eigenvalue problems as special cases. We formulate irreducibility and symmetry properties of a nonnegative tensor $T$ in terms of the associated shape partition. We recast the eigenvalue problem for $T$ as a fixed point problem on a suitable product of projective spaces. This allows us to use the theory of multihomogeneous order-preserving maps to derive a new and unifying Perron–Frobenius theorem for nonnegative tensors which either implies earlier results of this kind or improves them, as weaker assumptions are required. ... Read more
Visiting Tufts University
I will be visiting the Department of Mathematics of Tufts University in Boston, Massachusetts from Wednesday 20 to Friday 22 December.
SIAM ALA 18 Conference in Hong Kong
I am organizing a minisymposium and giving a talk at next SIAM Applied Linear Algebra conference in Hong Kong. Below are some detail of my contributions. This event is part of the research project MAGNET for which I would like to acknowledge support from the Marie Curie individual fellowship scheme.
Minisymposium: Nonlinear Perron-Frobenius theory and applications
jointly organized with Antoine Gautier
Abstract: Nonlinear Perron-Frobenius theory addresses problems such as existence, uniqueness and maximality of positive eigenpairs of different types of nonlinear and order-preserving mappings.In recent years tools from this theory have been successfully exploited to address problems arising from a range of diverse applications and various areas, such as graph and hypergraph analysis, machine learning, signal processing, optimization and spectral problems for nonnegative tensors. This minisymposium sample some recent contributions in this field, covering advances in both the theory and the applications of Perron-Frobenius theory for nonlinear mappings.
Speakers:
- Antoine Gautier (Saarland University, Germany)
- Francesca Arrigo (University of Strathclyde, UK)
- Shmuel Friedland (University of Chicago, USA)
- Jiang Zhou (Harbin Engineering University, China)
Contributed talk: A new Perron-Frobenius theorem for nonnegative tensors
Abstract: Based on the concept of dimensional partition we consider a general tensor spectral problem that includes all known tensor spectral problems as special cases. We formulate irreducibility and symmetry properties in terms of the dimensional partition and use the theory of multi-homogeneous order-preserving maps to derive a general and unifying Perron-Frobenius theorem for nonnegative tensors that either includes previous results of this kind or improves them by weakening the assumptions there considered.
Rome Moscow School 2018
I am very happy to hear from Carmine di Fiore that the 6th edition of the Rome Moscow summer school on Matrix Methods and Applied Linear Algebra will take place next summer, between August 25 and September 23, 2018.
This summer school is very peculiar because is long (one month!) and thus allows students to really work over the topics that are discussed. Also it is a wonderful occasion to meet new people in the field of Applied Linear Algebra. I have been student of several editions of the school and strongly encourage participation.
ZiF Final Conference
Getting ready for the ZiF final conference in Bielefeld. I will talk about the nodal domains of the $p$-Laplacian operator on discrete graphs.
Precisely, this is the abstract of my talk: The number of nodal domains induced by the eigenfunctions of the Laplacian operator has been completely described both for graphs and for continuous domains. For $p\geq 1$, the $p$-Laplacian is a nonlinear operator which reduces to the standard Laplacian when $p=2$. This nonlinear operator has gained popularity in recent years as, for instance, it can be used to improve data clustering algorithms. We consider a set of variational eigenvalues of the $p$-Laplacian on discrete graphs and analyze the nodal domain structure of the associated eigenfunctions. We show that when $p>1$, the upper bound in the linear nodal domain theorem carries over unchanged to the nonlinear setting, whereas some properties are lost when $p=1$. We also discuss an higher-order Cheeger inequality that can be obtained by exploiting the nodal structure of the $p$-Laplacian.
New paper out
Node and layer eigenvector centralities for multiplex networks
Abstract: Eigenvector-based centrality measures are among the most popular centrality measures in network science. The underlying idea is intuitive and the mathematical description is extremely simple in the framework of standard, mono-layer networks. Moreover, several efficient computational tools are available for their computation. Moving up in dimensionality, several efforts have been made in the past to describe an eigenvector-based centrality measure that generalizes Bonacich index to the case of multiplex networks. In this work, we propose a new definition of eigenvector centrality that relies on the Perron eigenvector of a multi-homogeneous map defined in terms of the tensor describing the network. ... Read more
New paper out
Modularity bounds for clusters located by leading eigenvectors of the normalized modularity matrix
Abstract: 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. ... Read more
New paper out
A modularity based spectral method for simultaneous community and anti-community detection
Abstract: In a graph or complex network, communities and anti-communities are node sets whose modularity attains extremely large values, positive and negative, respectively. We consider the simultaneous detection of communities and anti-communities, by looking at spectral methods based on various matrix-based definitions of the modularity of a vertex set. Invariant subspaces associated to extreme eigenvalues of these matrices provide indications on the presence of both kinds of modular structure in the network. ... Read more
--- Two communities and one anti-community coexist in the ‘‘Small World’’ citation network
New paper out
On the stability of network indices defined by means of matrix functions
Abstract: Identifying important components in a network is one of the major goals of network analysis. Popular and effective measures of importance of a node or a set of nodes are defined in terms of suitable entries of functions of matrices $f(A)$. These kinds of measures are particularly relevant as they are able to capture the global structure of connections involving a node. However, computing the entries of $f(A)$ requires a significant computational effort. ... Read more
New paper out
Community detection in networks via nonlinear modularity eigenvectors
Abstract: Revealing a community structure in a network or dataset is a central problem arising in many scientific areas. The modularity function $Q$ is an established measure quantifying the quality of a community, being identified as a set of nodes having high modularity. In our terminology, a set of nodes with positive modularity is called a module and a set that maximizes $Q$ is thus called leading module. Finding a leading module in a network is an important task, however the dimension of real-world problems makes the maximization of $Q$ unfeasible. ... Read more
--- Bipartition obtained by the linear (left) and nonlinear (right) spectral methods. Networks shown, from left to right: Electronic2, Drugs, and YeastS.
Starting at Strathclyde
Today is the first day of my new academic position as Marie Curie Fellow at the department of Mathematics and Statistics of University of Strathclyde.
New paper out
Euler-Richardson method preconditioned by weakly stochastic matrix algebras: a potential contribution to Pagerank computation
Abstract: Let $S$ be a column stochastic matrix with at least one full row. Then $S$ describes a Pagerank-like random walk since the computation of the Perron vector $x$ of $S$ can be tackled by solving a suitable M-matrix linear system $Mx = y$, where $M = I − \tau A$, $A$ is a column stochastic matrix and $\tau$ is a positive coefficient smaller than one. The Pagerank centrality index on graphs is a relevant example where these two formulations appear. ... Read more
New paper out
An Efficient Multilinear Optimization Framework for Hypergraph Matching
Abstract: Hypergraph matching has recently become a popular approach for solving correspondence problems in computer vision as it allows to integrate higher-order geometric information. Hypergraph matching can be formulated as a third-order optimization problem subject to the assignment constraints which turns out to be NP-hard. In recent work, we have proposed an algorithm for hypergraph matching which first lifts the third-order problem to a fourth-order problem and then solves the fourth-order problem via optimization of the corresponding multilinear form. ... Read more
--- Demo of matching results on Quynh Nguyen
New paper out
A nodal domain theorem and a higher-order Cheeger inequality for the graph p-Laplacian
Abstract: We consider the nonlinear graph $p$-Laplacian and its set of eigenvalues and associated eigenfunctions of this operator defined by a variational principle. We prove a nodal domain theorem for the graph $p$-Laplacian for any $p\geq 1$. While for $p>1$ the bounds on the number of weak and strong nodal domains are the same as for the linear graph Laplacian ($p=2$), the behavior changes for $p=1$. We show that the bounds are tight for $p\geq 1$ as the bounds are attained by the eigenfunctions of the graph $p$-Laplacian on two graphs. ... Read more
New paper out
The Perron-Frobenius theorem for multihomogeneous mappings
Abstract: The Perron-Frobenius theory for nonnegative matrices has been generalized to order-preserving homogeneous mappings on a cone and more recently to nonnegative multilinear forms. We unify both approaches by introducing the concept of order-preserving multi-homogeneous mappings, their associated nonlinear spectral problems and spectral radii. We show several Perron-Frobenius type results for these mappings addressing existence, uniqueness and maximality of nonnegative and positive eigenpairs. We prove a Collatz-Wielandt principle and other characterizations of the spectral radius and analyze the convergence of iterates of these mappings towards their unique positive eigenvectors. ... Read more
New paper out
Localization of dominant eigenpairs and planted communities by means of Frobenius inner products
Abstract: 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 on 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. ... Read more
New paper out
Generalized modularity matrices
Abstract: 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. ... Read more
New paper out
Clustering Signed Networks with the Geometric Mean of Laplacians
Abstract: Signed networks allow to model positive and negative relationships. We analyze existing extensions of spectral clustering to signed networks. It turns out that existing approaches do not recover the ground truth clustering in several situations where either the positive or the negative network structures contain no noise. Our analysis shows that these problems arise as existing approaches take some form of arithmetic mean of the Laplacians of the positive and negative part. ... Read more
New paper out
Lower triangular Toeplitz-Ramanujan systems whose solution yields the Bernoulli numbers
Abstract: We prove that the Bernoulli numbers satisfy some special lower triangular Toeplitz systems of linear equations. One of these systems has a strong link with eleven Ramanujan’s linear equations satisfied by the first eleven Bernoulli numbers. Please cite this work as: @article{difiore2016lower, title={Lower triangular Toeplitz--Ramanujan systems whose solution yields the Bernoulli numbers}, author={Di Fiore, Carmine and Tudisco, Francesco and Zellini, Paolo}, journal={Linear Algebra and its Applications}, volume={496}, pages={510--526}, year={2016}, publisher={Elsevier} }
New paper out
A note on certain ergodicity coefficients
Abstract: We investigate two ergodicity coefficients $\phi_{|| \cdot ||}$ and $\tau_{n-1}$, originally introduced to bound the subdominant eigenvalues of nonnegative matrices. The former has been generalized to complex matrices in recent years and several properties for such generalized version have been shown so far. We provide a further result concerning the limit of its powers. Then we propose a generalization of the second coefficient $\tau_{n-1}$ and we show that, under mild conditions, it can be used to recast the eigenvector problem $Ax = x$ as a particular $M$-matrix linear system, whose coefficient matrix can be defined in terms of the entries of $A$. ... Read more
New paper out
Adaptive matrix algebras in unconstrained minimization
Abstract: In this paper we study adaptive $L(k)QN$ methods, involving special matrix algebras of low complexity, to solve general (non-structured) unconstrained minimization problems. These methods, which generalize the classical BFGS method, are based on an iterative formula which exploits, at each step, an ad hoc chosen matrix algebra $L(k)$. A global convergence result is obtained under suitable assumptions on $f$. Please cite this work as: @article{cipolla2015adaptive, title={Adaptive matrix algebras in unconstrained minimization}, author={Cipolla, Stefano and Di Fiore, Carmine and Tudisco, Francesco and Zellini, Paolo}, journal={Linear Algebra and its Applications}, volume={471}, pages={544--568}, year={2015}, publisher={Elsevier} }
New paper out
On complex power nonnegative matrices
Abstract: Power nonnegative matrices are defined as complex matrices having at least one nonnegative integer power. We exploit the possibility of deriving a Perron–Frobenius-like theory for these matrices, obtaining three main results and drawing several consequences. We study, in particular, the relationships with the set of matrices having eventually nonnegative powers, the inverse of M-type matrices and the set of matrices whose columns (rows) sum up to one. Please cite this work as: @article{tudisco2015complex, title={On complex power nonnegative matrices}, author={Tudisco, Francesco and Cardinali, Valerio and Di Fiore, Carmine}, journal={Linear Algebra and its Applications}, volume={471}, pages={449--468}, year={2015}, publisher={Elsevier} }
New paper out
An algebraic analysis of the graph modularity
Abstract: 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. ... Read more
New paper out
Optimal Rank Matrix Algebras Preconditioners
Abstract: When a linear system $Ax = y$ is solved by means of iterative methods (mainly CG and GMRES) and the convergence rate is slow, one may consider a preconditioner $P$. The use of such preconditioner changes the spectrum of the matrix defining the system and could result into a great acceleration of the convergence rate. The construction of optimal rank preconditioners is strongly related to the possibility of splitting $A$ as $A = P + R + E$, where $E$ is a small perturbation and $R$ is of low rank. ... Read more
New paper out
A preconditioning approach to the Pagerank computation
Abstract: Some spectral properties of the transition matrix of an oriented graph indicate the preconditioning of Euler-Richardson (ER) iterative scheme as a good way to compute efficiently the vertexrank vector associated with such graph. We choose the preconditioner from an algebra $\mathcal U$ of matrices, thereby obtaining an ER-$\mathcal U$ method, and we observe that ER-$\mathcal U$ can outperform ER in terms of rate of convergence. The proposed preconditioner can be updated at a very low cost whenever the graph changes, as is the case when it represents a generic set of information. ... Read more