About Us

Graphs have long been recognized, both in research and in industry, as a suitable model for the relational structures of complex networks, either biological or synthetic.

In particular, understanding the graph structure of real data is important in the design of recommender systems, or drug discovery. However, this data can be large in practice: ranging from tens of thousands to millions of nodes.

Centrality indices can be used in order to rank the nodes (the links, respectively) in a network according to their relative importance, thus allowing to restrict further the analysis. Our main goal is to provide necessary and sufficient conditions for the design of local-search algorithms (gradient descent like) for the problem of computing a most central vertex, according to some popular centrality indices found in the literature (Harary, reach, closeness, betweenness, etc.). For that, we plan to investigate on the convexity and unimodality properties of the associated centrality functions.

We argue that local-search algorithms are at the core of Machine Learning based optimization methods. As such, we expect our new results to also find applications in Graph Learning.