Modular Structure of Complex Networks  Page description

Help  Print 
Back »

 

Details of project

 
Identifier
68669
Type K
Principal investigator Palla, Gergely
Title in Hungarian Komplex Hálózatok Moduláris Szerkezete
Title in English Modular Structure of Complex Networks
Keywords in Hungarian Komplex hálózatok, statisztikus fizika, modulok, csoportok, hierarchia
Keywords in English Complex networks, statistical physics, modules, communities, hierarchical structures
Discipline
Biophysics (Council of Physical Sciences)80 %
Physics (Council of Physical Sciences)20 %
Panel Physics
Department or equivalent Department of Biological Physics (Eötvös Loránd University)
Participants Derényi, Imre
Farkas, Illés
Pollner, Péter
Starting date 2007-07-01
Closing date 2010-12-31
Funding (in million HUF) 7.866
FTE (full time equivalent) 3.90
state closed project
Summary in Hungarian
A komplex hálózatok globális szerkezetét a sűrűbb részgráfoknak megfelelő modulok, csoportosulások egymáshoz való viszonya alakítja ki. A nemrégiben kifejlesztett Klikk Perkolációs Módszer (CPM) egy fontos lépést jelent a hálózati csoportosulások keresése terén, mert megengedi a csoportok közti átfedéseket. A jelenlegi pályázat célja egyfelől a hálózatok moduláris szerkezetének tanulmányozása a CPM segítségével, másfelől a CPM továbbfejlesztése.

Ezeken belül szeretnénk a hálózati modulok időfejlődésének statisztikus tulajdonságait vizsgálni társszerzőségi, telefonhívási és gazdasági hálózatokban.

Terveink közt szerepel különböző hálózat klaszterező eljárások összehasonlítása protein kölcsönhatási és egyéb biológiai hálózatokban.

A CPM továbbfejlesztésénél szeretnénk az egyes élek súlyát és irányát figyelembe venni a klaszterezés során, valamint elkerülni a ritkán előforduló sűrű hálózati magoknál tapasztalható lelassulást.

Végül szeretnénk a komplex hálózatok hierarchikus szerkezetét vizsgálni a CPM által nyert modulok segítségével.
Summary
The global organization of complex networks can usually be interpreted as the coexistence of their structural sub-units (modules, or communities), associated with more highly interconnected parts. The recently introduced Clique Percolation Method (CPM) enables the communities to overlap with each other, making a much needed step towards uncovering the modular structure of complex networks. The current project is planned on the one hand to make use of the CPM in the detailed analysis of the modular structure of complex systems, and also to further extend the abilities of the CPM itself.

We plan to study the statistical properties of community evolution in collaboration, phone-call, and economic networks.

We would like to systematically compare existing clustering methods (including CPM) for protein-protein interaction and other biological networks.

We are going to develop extensions to CPM that can take into account the weight and the directionality of the individual links in the network, and also avoid slowing down in extreme dense cores.

Finally, we are planing to study the hierarchical organization of complex networks based on the modules and the network of modules provided by CPM.





 

Final report

 
Results in Hungarian
Kidolgoztunk egy módszert, mely lehetővé teszi időben változó hálózatokban a csoportok nyomon követését. A csoportok időfejlődését nagyméretű társaskapcsolat hálózatokban vizsgáltuk és több érdekes összefüggést találtunk a csoportok mérete, időbeli változékonysága és fennmaradási valószínűsége között. Kiterjesztettük a klikk perkolációs módszert irányított- és súlyozott hálózatokra. Ezek segítségével számos nagyméretű valós hálózatot vizsgáltunk. Az irányított csoportosulások viselkedése két nagy osztályba sorolta a vizsgált rendszereket, a súlyozott hálózatoknál pedig érdekes élsúlyok korrelációkat fedtünk fel. A mikroRNS-ek és az általuk gátolt mRNS-ek hálózatát vizsgálva a klikk perkolációs módszer segítségével mikroRNS funkciós csoportokat sikerült beazonosítani, és a sejten belüli jelátviteli hálózatokban gyógyszer célpont fehérjék előrejelzéséhez fejlesztettünk bioinformatikai módszereket. A hálózati hierarchiához kapcsolódóan címkézett hálózatok statisztikai tulajdonságait vizsgálatuk olyan rendszerekben, ahol a címkék maguk is hierarchikusan szerveződnek. Eredményeink szerint a tanulmányozott hálózatok érdekes önhasonlóságot mutatnak a címke indukált részgráfokra történő leszűkítés esetén. A hierarchia tanulmányozásához kapcsolódóan kifejlesztettünk egy önhasonló, hierarchikus multifraktál élbekötési mértéken alapuló véletlen gráf generáló módszert. Megmutattuk, hogy ennek segítségével nagyon sokféle eltérő véletlen hálózat generálható le.
Results in English
We developed a method enabling the tracking of communities in time evolving networks. We studied the statistical properties of community evolution in large social networks, and revealed interesting non trivial relations between the size, stationarity and survival probability of communities. We extended the clique percolation method for handling directed- and weighted networks, and analyzed numerous real networks with these new algorithms. The behavior of the directed communities classified the examined systems into two major groups, whereas the studies of the weighted networks revealed interesting link weight correlations. We located functional units with the help of the clique percolation method in the network of microRNAs and their regulated mRNAs, and developed bioinformatical tools for signal transduction networks, helping the prediction of drug target proteins. Relating to the field of network hierarchy, we studied the statistical features of tagged networks where the tags were hierarchically organized. According to our results, the examined networks showed an interesting self similarity when restricted to the tag-induced sub-graphs. Relating to the studies of hierarchy, we developed a random graph generator based on self-similar, hierarchical multifractal link probability measure. We have shown, that this method is capable of generating random networks with very diverse properties.
Full text https://www.otka-palyazat.hu/download.php?type=zarobeszamolo&projektid=68669
Decision
Yes





 

List of publications

 
G. Palla, A.-L. Barabási and T.Vicsek: Quantifying social group evolution, Nature 446, 664-667, 2007
G. Palla, L. Lovász and T.Vicsek: Multifractal network generator, PNAS 107, 7640-7645, 2010
Boross G, Orosz K, Farkas I J: Human microRNAs co-silence in well-separated groups and have different predicted essentialities, Bioinformatics 25, 1063, 2009
Korcsmáros T , Farkas I J , Szalay M S, Rovó P, Fazekas D, Spiró Z, Böde C, Lenti K, Vellai T, Csermely P: Uniformly curated signaling pathways reveal tissue-specific cross-talks and support drug target discovery, Bioinformatics 26, 2042, 2010
G. Palla, I. J. Farkas, P. Pollner, I. Derényi and T. Vicsek: Directed network modules, New Journal of Physics 9, 186, 2007
I. J. Farkas, D. Ábel, G. Palla and T. Vicsek: Weighted network modules, New Journal of Physics 9, 180, 2007
G. Palla, I. J. Farkas, P. Pollner, I. Derényi and T. Vicsek: Fundamental statistical features and self-similar properties of tagged networks, New Journal of Physics 10, 123026, 2008
G. Palla, P. Pollner and T.Vicsek: Rotated multifractal network generator, Accepted for publication in JSTAT, arXiv:1101.2338, 2010
P. Pollner, G. Palla and T.Vicsek: Clustering of tag-induced subgraphs in complex networks., Physica A 389, 5887-5894, 2010
P. Pollner, G. Palla, D. Ábel, A. Vicsek, I. J. Farkas, I. Derényi and T. Vicsek: Centrality properties of directed module members in social networks, Physica A: Statistical Mechanics and its Applications 387, 4959-4966, 2008
G. Palla, T. Vicsek and A.-L. Barabási: Community dynamics in social networks, Fluctuation and Noise Letters 7, L273-L287, 2007
G. Palla, D. Ábel, I. J. Farkas, P. Pollner, I. Derényi, T. Vicsek: k-clique percolation and clustering, Handbook of Large-scale Random Networks, ed.: B. Bollobás, R. Kozma, D. Miklós, Chapter 9, p.369-408, 2009
G. Palla, P. Pollner, A.-L. Barabási and T. Vicsek: Social Group Dynamics in Networks, Adatptive Networks , ed.: T. Gross, H. Sayama, Chapter 2, p. 11-38,, 2009
Palla G. és Kertész J.: Szociofizika: humán kapcsolatok hálózata nagy skálán, Fizikai Szemle 2008/6. 217, 2008
Palla Gergely, Barabási Albert-László, Vicsek Tamás: Társas kapcsolatok hálózata, Természet Világa 139: (3) 108-110, 2008
Palla G., Derényi I., Farkas I, Pollner P. és Vicsek T: A természet és a társadalom komplex hálózataiban található átfedõ csoportosulások feltárása, Mûszaki Szemle (Az Erdélyi Magyar Mûszaki Tudományos Társaság kiadványa) 42/2008 9-18, 2008
G. Palla, T. Vicsek and A.-L. Barabási: Statistical Properties of Community Dynamics in Large Social Networks, Internatioal Journal of Agent Technologies & Systems 1(4), 1-16, 2009




Back »