A one-day workshop on
Computational Aspects of Complex Networks
Rome, December 6, 2024
From biological systems to computer science, from technical to informational networks, and from economic to social systems, Complex Networks are becoming pervasive in dozens of applications. This global phenomenon has led various scientific areas to focus their efforts on analyzing the structure of Complex Networks and how they operate. Each discipline has contributed its own techniques and perspectives, in particular, computer science and applied mathematics have introduced new computational tools and techniques to efficiently discover and exploit the most relevant properties of Complex Networks.
The primary goal of the one-day CACN Workshop is to bring together researchers from different scientific communities related to the computational aspects of Complex Networks, in order to stimulate new interactions among them. Another key part of the workshop is the poster session, open to both young and senior researchers, providing an opportunity to present their work, share insights, and foster further collaboration across diverse fields.
Nonbacktracking Centralities for Temporal Networks
Francesca Arrigo (Strathclyde University, UK)
Though seemingly they belong to two different worlds, matrix functions and network science have some degree of overlap thanks to a very simple fact; powers of the adjacency matrix count traversals in the underlying network. This concept in turn allows for the definition of centrality measures in terms of entries (or sums thereof) of functions of the adjacency matrix. In this talk, we will focus on discrete temporal networks, where edges appear and disappear over time, and on walks that are not allowed to revisit the node that they just left. We will present theory and results, as well as discuss challenges of such an approach.
The talk is based on a joint work with Des Higham (Edinburgh), Vanni Noferini (Aalto), and Ryan Wood (Aalto).
Complex networks in AI tasks: nature, models and challenges
Roberto Basili (University of Rome Tor Vergata, Italy)
AI problems usually involve a variety of network structures originating from the multidimensional nature of most of the involved inferences and tasks. Social networks as well as large scale knowledge bases (as those involved by medical problems) are just examples of large-scale complex graphs. There, the nature of the represented phenomena is specific to the individual applications and it demands domain and task specific representations and algorithms. Experiences in the formal treatment of such large-scale graphs will be surveyed to discuss the role of effective approaches to the induction of optimal representation structures and to the prediction of task specific AI agents. Neural models have been widely studied for inducing suitable representations of the underlying graphs as a side effect of the optimization of predictive functions. The role of optimization as a knowledge distillation and compression methodology will be thus analysed to survey current underlying challenges.
Bioinspired dynamics for network design
Vincenzo Bonifaci (Roma 3 University, Italy)
In wet-lab experiments, the slime mold Physarum polycephalum has demonstrated its ability to solve shortest path problems and to design efficient networks. For the shortest path problem, a mathematical model for the evolution of the slime is available and it has been shown in computer experiments and through mathematical analysis that the dynamics solves the shortest path problem. After briefly reviewing these results, we introduce a dynamics for a network design problem — the problem of constructing a network that efficiently supports a multi-commodity flow problem. We investigate the dynamics in computer simulations and analytically. The dynamics minimizes an objective combining the cost of the network and the cost of routing the demands through the network. We finally discuss the relation between the dynamics and the mirror descent method, a generalization of gradient descent.
Enforcing Katz and PageRank Centrality Measures in Complex Networks
Fabio Durastante (University of Pisa, Italy)
A centrality measure quantifies the relative importance of a node in a complex network. It involves computing a centrality score for each node using various definitions of importance, among the most widely used are the Katz, total communicability, eigenvector, PageRank, and matrix-function based centrality indexes. These scores represent the node's influence within the network, assuming that nodes with higher centrality scores are considered more central or influential. Network analysis applications of centrality measures include identifying central decision-makers, analyzing network dynamics, and studying the spread of information or epidemics.
In this talk I investigate the problem of enforcing a desired centrality measure in complex networks, while still keeping the original pattern of the network. Specifically, by representing the network as a graph with suitable nodes and weighted edges, the talk focuses on the computation of the smallest perturbation on the weights required to obtain a prescribed PageRank or Katz centrality index for the nodes. The approach presented here relies on optimization procedures that scale with the number of modified edges, enabling the exploration of different scenarios and altering network structure and dynamics.
The talk is based on a joint work with Stefano Cipolla (University of Southampton) and Beatrice Meini (University of Pisa).
Constrained graph partitioning by structured ODEs
Nicola Guglielmi (Gran Sasso Science Institute, Italy)
Synopsis: Fundamental properties of weighted graphs, such as connectivity and centrality, are characterized by eigenvalues or eigenvectors of matrices related to the weighted adjacency matrix, such as the graph Laplacian. Here we study exemplary problems of partitioning/clustering, which can be viewed as matrix nearness problems that refer to eigenvalues and eigenvectors of structured symmetric real matrices. We propose algorithms that do eigenvalue optimization without eigenvalues but work directly with the quadratic form (Rayleigh quotients). This requires only matrix-vector products and vector inner products. In this presentation, we will address the problem of constrained graph partitioning, particularly in the presence of constraints. We propose an iterative algorithm for computing a minimum cut of a given weighted undirected graph under constraints, e.g., cardinality, must-link, and cannot-link constraints. The algorithm changes the weights such that the second eigenvalue of the graph Laplacian is driven to zero. The connected components of the partitioned graph are then read off from the corresponding eigenvector, known as the Fiedler vector. The proposed algorithm only requires the computation of matrix-vector products with the graph Laplacian and vector inner products but no computations of eigenvalues and eigenvectors. It is a two-level algorithm that follows a graph diffusion equation into a stationary point in the inner iteration and determines the minimum cut in the outer iteration.
The talk is based on a joint work with C. Lubich (Universität Tübingen).
Opinion Dynamics and Community Structure in Networks
Emanuele Natale (Université Côte d'Azur, France)
This talk presents some joint results that connect the behavior of simple opinion dynamics, such as the 2-majority and the averaging one, to the community structure of networks (focusing on the stochastic block model). In particular, we show that, if we interpret the 2-majority as a toy model of social conformism, an underlying community structure can quickly lead to polarization of opinions in the networks which persists for a long time. On the other hand, we show how a simple process such as the averaging dynamics can be leveraged to identify the underlying community structure.
Bilevel optimization with a lower-level contraction: Optimal sample complexity without warm-start
Saverio Salzo (University of Rome La Sapienza, Italy)
We analyse a general class of bilevel problems, in which the upper-level problem consists in the minimization of a smooth objective function and the lower-level problem is to find the fixed point of a smooth contraction map. This type of problems include instances of meta-learning, equilibrium models, hyperparameter optimization and data poisoning adversarial attacks. Several recent works have proposed algorithms which warm-start the lower-level problem, i.e. they use the previous lower-level approximate solution as a starting point for the lower-level solver. This warm-start procedure allows one to improve the sample complexity in both the stochastic and deterministic settings, achieving in some cases the order-wise optimal sample complexity. However, there are situations, e.g., meta learning and equilibrium models, in which the warm-start procedure is not well-suited or ineffective. In this work we show that without warm-start, it is still possible to achieve order-wise (near) optimal sample complexity. In particular, we propose a simple method which uses (stochastic) fixed point iterations at the lower-level and projected inexact gradient descent at the upper-level, that reaches an ε-stationary point using O(ε^(-2)) and Õ(ε^(-1)) samples for the stochastic and the deterministic setting, respectively. Compared to methods using warm-start, our approach yields a simpler analysis that does not need to study the coupled interactions between the upper-level and lower-level iterates. Finally, time permitting, we will discuss the extension of the theory to nonsmooth bilevel problems.
Topological Preconditioner for Higher-Order Laplacians
Francesco Tudisco (The University of Edinburgh, UK)
Models and methods for higher-order interactions in complex networks are a key focus of modern network science. When these interactions are represented using simplicial complexes, many existing approaches require solving least square problems where the Hodge Laplacian acts as the coefficient matrix. While fast topological preconditioners are well-established for standard graph Laplacians, thanks to advancements in graph spectral sparsifiers, these techniques do not readily extend to higher-order Laplacians. In this paper, we introduce the notion of an optimal collapsible subcomplex and propose a fast combinatorial algorithm to compute a sparse Cholesky-like preconditioner specifically for Hodge Laplacians. We evaluate the preconditioner’s effectiveness using the conjugate gradient method for least squares across a variety of simplicial complexes with different dimensions and edge densities. Our results show that, for sparse simplicial complexes, the proposed preconditioner significantly improves the condition number and outperforms the standard incomplete Cholesky factorization in terms of computational efficiency.
The talk is based on a joint work with Anton Savostianov and Nicola Guglielmi.