We adopt the so-called Computational-Lens approach [Karp11] to study self-organizing, intelligent phenomena on Complex Networks and Multi-Agent Systems [ABV08,Hofstad17]. Typically this complex behavior emerges as the outcome of the so-called Complexity_from_Simplicity phenomenon: The presence of some local, elementary local algorithm, running over a network formed by computationally-limited agents, often yields surprising forms of Swarm Intelligence such as the ability to solve a computationally-hard global task (clustering, opinion consensus, synchronization).

We thus develop models describing Complex Networks and Multi-Agent Systems and their evolution in time, we design and analyze distributed algorithms (or protocols) to solve fundamental networking tasks and we study the outcomes of the processes resulting from the interplay between the network models and the algorithms mentioned above.

Models. We are mainly interested in three types of Network models:

1. Foundational Probabilistic-Generative Models, such as: Erdös-Renyi graphs; preferential-attachment and fixed degree-distribution graphs; Power-Laws “Small-World” models such as Kleinberg’s and Watts-Strogatz’s [EK10, Hofstad17];

2. Models in which a network emerges as the result of agents activating links among themselves according to certain local rules, such as in the formation of Peer-to-Peer Overlay Networks in decentralized protocols (e.g. in Bitcoin), or the formation of Ad-Hoc Radio Networks in wireless contexts, or when edges of an underlying network are removed in order to sparsify the network while retaining certain desired properties [APR16, BSST13, BCPTZ21,CMPS10].

3. Network Formation Games, in which a network emerges as the result of an interaction between selfish players. The outcome of the interaction is usually modeled as some type of equilibrium. Typical research questions are the existence of such equilibrium, the computational complexity to find it, the study of the dynamics converging to it, and the quality of the equilibrium compared with some social optimal outcome [BGP15,BGLP16,FGLM22].

Some of the above Network-Formation models are well investigated in the static case, and one of the major novelties of our investigation is to focus on dynamic frameworks, in which, over time, nodes enter and exit the network (node churn), and/or edges are activated and deactivated. For other models, there are fundamental questions that still remain open even in the static case [BCPTZ21].

Algorithms. Our algorithmic research activity focuses mostly on the following set of fundamental tasks.

Information Diffusion. The adoption of an idea or rumor through a Social Network, the consumption of a new product in a marketplace, the risk of receiving a computer virus through the World Wide Web, or the spreading of a disease through a population are just a few, popular instances of Information-Diffusion protocols in Complex Networks [ABV08,EK10]. Computational tasks in computer networks, synchronization and searching tasks in Biological Systems, opinion formation, polarization, and consensus in Social Networks are all fundamental activities that have been proven to follow basic information-diffusion protocols such as epidemic models, probabilistic flooding, push-pull mechanisms, label-propagation algorithms, and majority rules [ABV08,APR16, BCN20,EK10,Shah09]. In particular, the proper modeling and analysis of epidemic processes has been a long-standing area of research. One of the earliest epidemic models was conceived by Bernoulli in 1760, motivated by the spread of smallpox. Recent years saw a resurgence of interest in these topics as the concept of Complex Networks are becoming increasingly prevalent in modeling many different aspects of the world today. New, refined models and tools have been recently applied to many different information-spreading protocols on Complex Networks [EK10,Hae15,PCVV15].

Research Challenges. Broadcasting Processes in which initially one or more nodes of the network hold a certain piece of information, and wish to broadcast it to the other nodes of the network, with the edges of the network modelling communication links among nodes. Epidemic processes, in which a communicable disease spreads through social interactions, have similar mathematical models. We study Information-Diffusion processes in time-evolving models and to study Epidemic processes in network models studied in the literature on Social Networks, such as the models of Kleinberg and of Watts-Strogatz. In the above settings the major scientific questions are the following. Given a network, where links represent who has the potential to inform/infect whom, what can we say about its epidemic threshold? That is, can we determine whether a small initial infection can ‘take-off’ and create an epidemic? Which is its propagation speed (i.e., its stabilization time)? What will change if nodes/edges follow a time-evolving behavior? Both the underlying (dynamic) network (or the population structure) and the particular local propagation protocol should intuitively play an important role in the spread of contagions (viruses/memes/products) [APR16, BCDPTZ22,CMMPS10,Shah09].

Consensus Processes. Relying on information diffusion phenomena, collective or group decision-making pertains to computational, social and biological systems. One of its most basic forms is Consensus, which plays a key role in coordinating networks of agents or social groups. Implementing Consensus algorithms in a distributed fashion is a challenging problem in several network models. Yet, one can observe several examples of communities that achieve highly sophisticated forms of Consensus, examples being bacterial populations and social insects, which use quorum-sensing algorithms to collectively solve complex decision problems [DW13]. In general, the performances of algorithmic protocols that achieve more or less sophisticated forms of collective decision-making are affected by the underlying network structure in non-obvious ways [BCN20]. At the same time, this network-dependent evolution can be leveraged algorithmically in some cases , but a satisfactory picture of this complex interplay is largely missing [BCN20,DCN22].

Research Challenges. Network processes in which each node initially holds an opinion or senses a value from the environment, nodes communicate their opinion to some of their neighbors, and the desired final state is for all nodes to share the same opinion. We propose to study simple decentralized Consensus protocols in static and dynamic/noisy networks, a setup that does not yet have a satisfactory rigorous treatment [BCNPT16,DCN22].

Mining Complex Networks. Algorithms whose goal is to recover key features of the underlying network, such as computing Maximal Independent Sets, or discovering Clusters/Communities, or, in Multi-Agent Systems, searching for a target node/point (e.g. a treasure) of the agent’s support graph/space [EetAl07, FKR16].

Research Challenges. The general challenge arising in such applications is essentially due to the following scenario: simple and natural algorithms, somewhat inspired by social behavior, often yield promising solutions of the original task, but its rigorous analysis is far from trivial. Typical instances of this complex behavior are: (i) the use of Label Propagation and Averaging Dynamics for Community Detection in Social Networks [BCNPT20a] and (ii) the use of parallel randomized search strategies for agent swarms [CDGN20].

We investigate a range of theoretical and practical aspects of algorithmics, with a particular emphasis on problems emerging from complex networks and fault-tolerance scenarios.

Some of the research topics we work on are:

Spanners, distance oracles and temporal graphs

A spanner is a sparse subgraph of a graph that preserves some property of interest such as reachability or distances among vertices, while an oracle is a compact data structure that quickly answers queries about such property. An example is the problem of finding a subgraph of small size (i.e., with few edges) that preserve the distance between any pair of vertices up to a multiplicative stretch factor. A typical goal is to understand the stretch-size tradeoffs that can be obtained.

Spanners and oracles received a huge amount of attention by the research community, due to their applicability in basic communication network problems, distributed systems, robotics, and more (see [ABSHJ20] for a survey).

We worked a lot on spanners and oracles in the fault-tolerance setting, in which you want to find good spanners/oracles that preserve some property even when some network components can fail. Another emerging research topic we contribute to is the study of spanners for temporal graphs. Temporal graphs are graphs in which an edge is only available in some specific time instants, and this allows modeling time-evolving networks such as transportation networks or computer networks in which not all resources are always available.

A couple of our works on the topic: [BGLP22,BDGL22].

Fault-tolerance and augmenting network problems

We love algorithmic problems arising from fault-tolerance scenarios, in which in general you want a system to remain operational even when some (usually few) of its components can fail. Problems of this kind cover a wide range of settings and challenges, like the design of resilient data structures (data structures that are required to withstand memory faults), or the computation of good recovery solutions of a tree-based communication networks subject to transient link failures. A complementary scenario is when the goal is to augment a network in order to improve some of its efficiency measures, like reducing the diameter or augmenting the degree of connectivity.

A few of our works on the topic: [GLZ21,BCGLP20,BGP12].

The Senior Team is formed by Professors Andrea Clementi, Luciano Gualà, and Francesco Pasquale that deeply and regularly collaborate on the above research topics with other members from different Institutions. In particular, we highlight the deep and regular collaborations with the following internationally renowned researchers:

• Prof. Luca Becchetti (Sapienza University of Rome)

• Prof. Davide Bilò (University of L’Aquila)

• Prof. Pierluigi Crescenzi (GSSI, L’Aquila)

• Prof. Stefano Leucci (University of L’Aquila)

• Prof. Emanuele Natale (INRIA and CNRS Researcher, France – He is also a permanent member of the Scientific Board of our PhD School in Data Science)

• Prof. Luca Trevisan (Bocconi University of Milan)

The Senior Team benefits from the presence some young researchers (PhD Students and Postdocs). The current set of Phd and Post-Doc students include:

• Antonio Cruciani

• Riccardo Denni

• Fabio Giacomelli

• Luca Pepè Sciarria

• Mirko Rossi

The activities are organized in working groups that collaborate in weekly meetings on specific research topics.

[ABSHJ20] A.R. Ahmed, G. Bodwin, F.D. Sahneh, K. Hamm, M.J.L. Jebelli, S.G. Kobourov, R. Spence, Graph spanners: A tutorial review, Comput. Sci. Rev., 2020.

[ABV08] Alain, B., Barthelemy, M., and Vespignani, A. Dynamical processes on complex networks. Cambridge university press, 2008.

[APR16] Augustine, J., Pandurangan, G., & Robinson, P. (2016). Distributed algorithmic foundations of dynamic networks. ACM SIGACT News, 47(1), 69-98.

[BSST13] Batson, J., Spielman, D. A., Srivastava, N., & Teng, S. H. (2013). Spectral sparsification of graphs: theory and algorithms. Communications of the ACM, 56(8), 87-94.

[BCNPT16] Becchetti, L., Clementi, A., Natale, E., Pasquale, F., & Trevisan, L. (2016). Stabilizing consensus with many opinions. In Proceedings of the twenty-seventh annual ACM-SIAM symposium on Discrete algorithms (pp. 620-635). Society for Industrial and Applied Mathematics.

[BCN20] Becchetti, L., Clementi, A., & Natale, E. (2020). Consensus dynamics: An overview. ACM SIGACT News, 51(1), 58-104.

[BCNPT20a] Becchetti, L., Clementi, A. E., Natale, E., Pasquale, F., & Trevisan, L. (2020). Find your place: Simple distributed algorithms for community detection. SIAM Journal on Computing, 49(4), 821-864.

[BCNPT20b] Becchetti, L., Clementi, A., Natale, E., Pasquale, F., & Trevisan, L. (2020). Finding a bounded-degree expander inside a dense one. In Proceedings of the Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms (pp. 1320-1336). Society for Industrial and Applied Mathematics.

[BCPTZ21] Becchetti, L., Clementi, A., Pasquale, F., Trevisan, L., and Ziccardi, I (2021). Expansion and flooding in dynamic random networks with node churn. 2021 IEEE 41st International Conference on Distributed Computing Systems (ICDCS). IEEE.

[BCDPTZ22] Becchetti, L., Clementi, A., Denni, R., Pasquale, F., Trevisan, L., & Ziccardi, I. (2022, October). Percolation and Epidemic Processes in One-Dimensional Small-World Networks. In LATIN 2022: Theoretical Informatics: 15th Latin American Symposium, Guanajuato, Mexico, November 7–11, 2022, Proceedings (pp. 476-492). Cham: Springer International Publishing.

[BCGLP20] D. Bilò, F. Colella, L. Gualà, S. Leucci, G. Proietti, An Improved Algorithm for Computing All the Best Swap Edges of a Tree Spanner. Algorithmica 82(2): 279-299 (2020).

[BGLP16] Bilò D., Gualà L., Leucci S., Proietti G. Locality-Based Network Creation Games. ACM Trans. Parallel Comput. 3(1): 6:1-6:26.

[BGP15] Bilò D., Gualà L., Proietti G. Bounded-Distance Network Creation Games. ACM Trans. Economics and Comput. 3(3): 16:1-16:20 (2015).

[BGLP22] D. Bilò, L. Gualà, S. Leucci, G. Proietti, Multiple-Edge-Fault-Tolerant Approximate Shortest-Path Trees, Algorithmica, 2022.

[BDGL22] D. Bilò, G. D’Angelo, L. Gualà, S. Leucci, M. Rossi, Sparse Temporal Spanners with Low Stretch. ESA 2022.

[BGP12] D. Bilò, L. Gualà, G. Proietti, Improved approximability and non-approximability results for graph diameter decreasing problems, TCS 2012.

[CMMPS10] Clementi, A. E., Macci, C., Monti, A., Pasquale, F., & Silvestri, R. (2010). Flooding time of edge-markovian evolving graphs. SIAM journal on discrete mathematics, 24(4), 1694-1712.

[CDGN20] Clementi, A., d’Amore, F., Giakkoupis, G., & Natale, E. (2021, July). Search via parallel lévy walks on z2. In Proceedings of the 2021 ACM Symposium on Principles of Distributed Computing (pp. 81-91).

[DCN22] D’Amore, F., Clementi, A., & Natale, E. (2022). Phase transition of a nonlinear opinion dynamics with noisy interactions. Swarm Intelligence, 1-44.

[DW13] Diggle, S. P., & Williams, P. (2013). Quorum Sensing. Brenner’s Encyclopedia of Genetics.

[EK10] D. Easley, J. Kleinberg (2010). Networks, crowds, and markets. Cambridge.

[EetAl07] Edwards, A. M., Phillips, R. A., Watkins, N. W., Freeman, M. P., Murphy, E. J., Afanasyev, V., … & Viswanathan, G. M. (2007). Revisiting Lévy flight search patterns of wandering albatrosses, bumblebees and deer. Nature, 449(7165), 1044-1048.

[FKR16] Fraigniaud, P., Korman, A., & Rodeh, Y. (2016, June). Parallel exhaustive search without coordination. In Proceedings of the forty-eighth annual ACM symposium on Theory of Computing(pp. 312-323).

[FGLM22] Friedrich T., Gawendowicz H., Lenzner P., Melnichenko A. Social Distancing Network Creation. ICALP 2022: 62:1-62:21.

[GLZ21] L. Gualà, S. Leucci, I. Ziccardi, Resilient Level Ancestor, Bottleneck, and Lowest Common Ancestor Queries in Dynamic Trees. ISAAC 2021.

[Hofstad17] van der Hofstad, R. (2017). Random Graphs and Complex Networks. Cambridge,

[Karp11] Karp, R.M. (2011). Understanding science through the computational lens. Journal of Computer Science and Technology 26.4.

[Shah09] Shah, D. (2009). Gossip Algorithms, Now Publishers Inc.