Lecture
LCN2 Seminar: Convexity in complex networks
- Lovro Šubelj
- Date
- 22 September 2017
- Time
- Address
- Snellius Building
Niels Bohrweg 1
2333 CA Leiden - Room
- 402
About the talk
Speaker: Lovro Šubelj (University of Ljubljana, Slovenia)
Title: Convexity in complex networks
Abstract:
In this talk, I will present a methodology for measuring convexity in networks [1]. Convexity is a property of a part of a mathematical object that includes all the shortest paths between its units. In the case of networks, a connected induced subgraph is said to be convex if every shortest path between the nodes of the subgraph lies entirely within the subgraph. Fully convex network would therefore be a collection of cliques stitched together in a tree. Such definition of convexity allows us to categorize networks into four classes:
- globally convex (e.g. technological networks),
- regionally convex (e.g. core-periphery networks),
- locally convex (i.e. random graphs) and
- non-convex (e.g. food webs).
In the remainder of the talk, we will consider the largest high-convexity parts of empirical networks called convex skeletons [2]. A convex skeleton is a generalization of a spanning tree in which each edge can be replaced by a clique. I will show that convex skeletons retain the network degree distribution, clustering, connectivity and also distances between the nodes, while making the shortest paths between the nodes largely unique. A convex skeleton thus represents a very simple definition of a network backbone that retains its most important properties.
If time permits, I will also discuss some preliminary results on applications of convexity in citation networks such as revealing most important intermediate papers between selected focal papers.
References
[1] Marc, T., & Šubelj, L. (2017). Convexity in complex networks. Network Science, pp. 27, in press, arXiv:1608.03402.
[2] Šubelj, L. (2017). Convex skeletons of complex networks. arXiv:1709.00255, pp. 11.
The seminar will be followed by drinks and snacks in the Foobar in the same building (17:00-18:00 hrs).
About the LCN2 seminar
This talk is part of a series of seminars organized within an ongoing scientific initiative called "Leiden Complex Networks Network (LCN2), which aims at bringing together scientists with a common interest in both theoretical models and empirical analyses of complex networks and random graphs. The LCN2 community that is being established shares the approach of using networks for describing real-world complex systems and aims at developing related analytical and numerical methods, while also being open to other research approaches for studying complex systems. The talks are designed for a broad audience, allowing for constructive exchanges of ideas between scientists from different disciplines. After the talk, some drinks and simple snacks are provided.