Our theoretical research activity essentially focuses on two main, mutually-related topics.

We adopt the so-called Computational-Lens approach to study self-organizing and intelligent phenomena on Complex Networks and Multi-Agent Systems. Typically, this complex behavior emerges as the outcome of the Complexity-from-Simplicity phenomenon: the presence of simple local algorithms running over networks of computationally-limited agents often yields surprising forms of Swarm Intelligence, such as the ability to solve computationally-hard global tasks (e.g., clustering, opinion consensus, synchronization)

We develop models describing Complex Networks and Multi-Agent Systems and their evolution over time, and we design and analyze distributed algorithms (or protocols) to solve fundamental networking tasks. We also study the interaction between network models and algorithms.

We focus mainly on three types of network models:

a. Foundational probabilistic-generative models

Examples include Erdős–Rényi graphs, preferential-attachment models, fixed degree-distribution graphs, and power-law small-world models such as Kleinberg’s and Watts–Strogatz’s.

b. Emergent network models

In these models, networks emerge from agents activating links according to local rules, as in peer-to-peer overlay networks, decentralized protocols, ad-hoc radio networks, or sparsification processes where edges are removed while preserving desired properties.

c. Network formation games

Here, networks emerge from interactions between selfish agents. Research questions include the existence and computation of equilibria, convergence dynamics, and comparison with socially optimal outcomes.

Many of these models are well understood in static settings. A major novelty of our research is the focus on dynamic frameworks, where nodes enter or leave the network (node churn) and edges appear or disappear over time.

Our algorithmic research focuses on the following fundamental tasks.

Information diffusion models describe how ideas, rumors, products, viruses, or diseases spread over networks. Applications range from social networks and biological systems to computer networks.

These processes are often modeled through epidemic protocols such as flooding, push–pull mechanisms, label propagation algorithms, and majority rules. Epidemic models date back to Bernoulli’s work in 1760 and remain central today due to the relevance of complex networks in modeling real-world systems.

Research challenges include:

• effects of time-evolving networks and dynamic interactions

• epidemic thresholds,

• propagation speed and stabilization time,

Consensus is a fundamental mechanism for collective decision-making in computational, social, and biological systems. Implementing distributed consensus algorithms is challenging in many network models, yet natural systems such as bacterial colonies and social insects achieve consensus through mechanisms like quorum sensing.

The performance of consensus protocols depends strongly on the underlying network structure, and understanding this interplay remains an open research problem.

Research challenges include studying decentralized consensus protocols in static, dynamic, and noisy networks.

This area focuses on algorithms for extracting key properties of networks, such as:

• maximal independent sets,
• cluster and community detection
• search problems in multi-agents systems.

Research challenges arise because simple, socially inspired algorithms often perform well in practice but are difficult to analyze rigorously. Examples include label propagation and averaging dynamics for community detection, as well as randomized parallel search strategies.

We investigate theoretical and practical aspects of algorithmics with emphasis on complex networks and fault tolerance.

A spanner is a sparse subgraph that approximately preserves distances, while a distance oracle is a compact data structure that answers distance queries efficiently. Key research goals include understanding stretch–size trade-offs.

We study spanners and oracles in fault-tolerant settings and in temporal graphs, where edges are available only at certain times, modeling time-evolving systems such as transportation or communication networks.

We study algorithmic problems where systems must remain operational despite failures. Topics include resilient data structures, recovery strategies for communication networks, and network augmentation to improve efficiency measures such as diameter or connectivity.

The senior team consists of professors who collaborate regularly on the above topics with researchers from various institutions. The group also includes PhD students and postdoctoral researchers.

Research activities are organized into working groups that meet weekly to collaborate on specific topics.

A comprehensive list of papers and books related to this research activity is maintained separately and regularly updated:

[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.