Daniela Bubboloni, professor at the Department of Mathematics and Computer Science “Ulisse Dini” of the University of Florence, was our guest to the D2 seminar presenting his study entitled:  Paths and flows for centrality measures in networks”

During your presentation you mentioned that your project was born as a conceptual clarification of a certain terminology, so how would you explain to someone who is not an expert of centrality measures or doesn’t know what paths and flows are what your study is about? 

Networks are models for a large variety of phenomena, and their characteristics and properties are at the core of the international research. Since networks are usually very large, it is with no doubt interesting to isolate single vertices or groups of vertices which play the main role in a given network, the so-called central vertices. That allows to concentrate the attention on the most important aspects describing the phenomenon under consideration, reducing the complexity given by the big amount of data encoded by the whole network and focusing on a subset of vertices accurately chosen. The group centrality measures play the important role to detect those special groups of vertices and have been copiously proposed since the 50’s as social science instruments. Nowadays they have become a tool largely used in physics and biology as well as in sociology, finance and engineering.
During the years many centrality measures have been proposed. However, it seems that flows had not played yet, in the context of centrality, the deep role that they would deserve. The mathematical concept of flow aims to describe the various ways in which pipelines can be filled pumping something (water, electricity etc.) from a source to a destination called sink, without breaking the pipeline. The idea is that every part of a pipeline between two junctions is subject to a particular upper bound, called capacity, for the amount of that something circulating in it.
Finding a maximum flow means to find those flows which tolerate the maximum amount of pumping from the source. A very concrete idea which is formalized as an abstract object and then becomes a tool for studying many unexpected situations both theoretical (graph theory and connectivity problems) and practical (transportation problems, vehicle networks, assignment of one-way streets etc.).
A path is a natural idea which arises looking to the drawing of a network. Looking at the arrows you are invited to follow them one after another one. Starting at a vertex and arriving to another one you have travelled along a path. Now imagine a junction of capacity c as splitted into c single junctions of capacity 1. If you have a sequence of junctions of capacity at least one from the source to the sink, you can easily imagine a single pipeline from the source to the sink and see a path from the source to the sink. On the other hand surely you can pump just one unit from the source and let it flow exactly through the considered sequence of junctions. This helps you guess an interplay between flows and paths. The exact formal explanation of that link was missing in the literature. In the papers appeared in the literature about flow centrality measures, there is a mixture of terminology, jumping from paths to flows, which was not formally justified. We discovered that some intuition was right, but some naive extensions of that intuition is wrong and hence in some applications one needs to distinguish the path approach to the flow approach. This holds, for instance, in dealing with flow centrality for groups of vertices instead of single vertices.

Could you give us a glimpse of possible applications or future outcomes of your research?

In the scientific literature, the centrality measures have been used more to confirm known phenomena than to forecast the phenomena themselves. We would instead like to develop the huge potential that centrality considerations could have in designing networks and understanding which configurations of its vertices realize the better scenario.
Centrality could be a peculiar ingredient for designing a network and thus very useful for engineering applications. One of our flow group centrality measures takes into consideration how much the network is damaged in terms of flow when all the connections through a group of vertices get lost. That allows, for instance, to recognize the groups of vertices on which it is important to focus for the network maintenance in order to avoid the maximum decrease of global flow. Centrality can mean many things: power, prestige, authority, best betweenness position. Applications of centrality measure vary from detecting the central elements of a terrorist network to discover the genes which are most responsible for the development of cancer. This wide range of applications is somewhat at the base of the impossibility to uniquely decide which measure is “the best”. On the other hand, we surely need to understand which measure is better in a certain context. We believe that the main tool for reaching this control on the centrality measures is isolating some relevant properties that a centrality measure could reasonably have, and then use those properties to discriminate one centrality measure from another one. For that reason a great part of the research of my team is, at the moment, devoted to isolate and study the properties of group centrality measures. Another part of the research is about the application of our two group centrality measures to concrete networks in order to empirically discover if they behave better than other measures. We are in particular planning to deal with Trade Networks.

Daniela Bubboloni is also a member of our center. More information about his research can be found on her personal page.

You can access the recording of this seminar through this link. (Registration needed)

Reference: D. Bubboloni, M. Gori, Paths and flows for centrality measures in networks, Networks (2022). You can download the full paper here.