Anna Pidnebesna, David Hartman, Daniel Trlifaj, Aneta Pokorna, and Jaroslav Hlinka

Department of Complex Systems

Institute of Computer Science of the Czech Academy Sciences

Location: Institute of Computer Science, Pod Vodárenskou věží 2, 180 00 Prague, Czechia

   Room 318

Date:   Tuesday 18 February 2025

Time: 13:00 CET

ZOOM: Time: Feb 18, 2025 01:00 PM Prague Bratislava

https://cesnet.zoom.us/j/92370723985?pwd=8wwrgBbu4OiUrObFPxIiKcWol75YgN.1 

Meeting ID: 923 7072 3985

Passcode: 442555

Abstract:

When studying complex networks in general and biological networks in particular, the ability to characterize graphs plays an important role. Various theoretical graph measures have become a popular and valuable tool in this context. As a representative of those measures, degree distribution is an easy but powerful characteristic widely used to describe and compare the graphs.  Despite its popularity, the degree distribution has a limited descriptive property. The graphlets were recently introduced by Pržulj (2007) [1] as an extension of the degree distribution notion by considering the more distant neighborhood of a node. Graphlets are shown to be a good tool for characterizing the local topology of the graph, which opens a wide field of usability.

In our study, we explore the basic properties of graphlets and their applicability in several tasks, such as comparison of the models or classification tasks involving simulated and real data. We study the graphlets of several widely-used random graph models such as Erdos-Renyi, Barabasi-Albert, and random geometric models. We also present the analysis of the human brain data, in particular, the graphs obtained from the functional connectivity computed from the resting-state fMRI.

Keywords: graphlets, degree distribution, random graph models, fMRI, brain

References: 

1. Nataša Pržulj, Biological network comparison using graphlet degree distribution, Bioinformatics, Volume 23, Issue 2, January 2007, Pages e177–e183, https://doi.org/10.1093/bioinformatics/btl301

2. Yaveroğlu, Ö. N., Davis, D., Levnajic, Z., Janjic, V., Karapandza, R., Stojmirovic, A., & Pržulj, N. (2014). Revealing the Hidden Language of Complex Networks. Scientific Reports, 4(1), 1-9. https://doi.org/10.1038/srep04547

3. J. Crawford and T. Milenković, "GREAT: GRaphlet Edge-based network AlignmenT," 2015 IEEE International Conference on Bioinformatics and Biomedicine (BIBM), Washington, DC, USA, 2015, pp. 220-227, https://doi.org/10.1109/BIBM.2015.7359684 

4. Pržulj, N. (2014). GR-Align: Fast and flexible alignment of protein 3D structures using graphlet degree similarity. Bioinformatics, 30(9), 1259-1265. https://doi.org/10.1093/bioinformatics/btu020