Hierarchical organisation in complex systems  Page description

Help  Print 
Back »

 

Details of project

 
Identifier
105447
Type K
Principal investigator Palla, Gergely
Title in Hungarian Hierarchikus szerveződés komplex rendszerekben
Title in English Hierarchical organisation in complex systems
Keywords in Hungarian hierarchia, hálózatok, címkék, ontológiák, csoportok, multifraktálok
Keywords in English hierarchy, networks, tags, ontologies, communities, multifractals
Discipline
Physics (Council of Physical Sciences)100 %
Ortelius classification: Statistical physics
Panel Physics
Department or equivalent Department of Biological Physics (Eötvös Loránd University)
Participants Méhes, Előd
Pollner, Péter
Tibély, Gergely
Starting date 2012-09-01
Closing date 2017-02-28
Funding (in million HUF) 27.172
FTE (full time equivalent) 9.44
state closed project
Summary in Hungarian
A kutatás összefoglalója, célkitűzései szakemberek számára
Itt írja le a kutatás fő célkitűzéseit a témában jártas szakember számára.

Komplex rendszerek hierarchikus szerveződését tervezzük kutatni új szempontok szerint. Egyfelől a címkézett hálózatokkal kapcsolatos korábbi kutatásainkat terjesztenénk ki online címkéző rendszerekre, melyekben a felhasználók szabadon választott szavakkal címkézhetnek különböző objektumokat (pl. könyveket, fotókat, webcímeket). A címkéknek itt nincs egy előre definiált hierarchiája, mindazonáltal feltehető, hogy a felhasználók gondolkodása bizonyos mértékig hierarchikus, pl. a többség számára a „puli” valószínűleg a „kutya” speciális esete. Szeretnénk egy statisztikus fizikai alapokon nyugvó megközelítést kidolgozni a rejtett hierarchia (ontológia) felderítésére. A heurisztikus módszerek mellett a kinyert ontológiák minőségét kvantitatívan is mérni szeretnénk a rendelkezésre álló címke-statisztikák alapján. Ehhez kifejlesztenénk egy kontrollálható sztochasztikus tesztrendszert is, melyen a különböző ontológia-felderítő algoritmusok összevethetők. Az elméleti eredményeket valós adatokon is szeretnénk tesztelni.
A hierarchiához és a címkékhez kapcsolódóan keresnénk a hálózati csoportok optimális címkézési módszerét a csoporttagok címkéi alapján. A kutatás e része szervesen kötődik a csoportkeresés terén elért korábbi eredményeinkhez, melyeken felül természetes nyelvfeldolgozó módszerek bevonását is tervezzük.
Továbbá szeretnénk továbbfejleszteni a csoportunk által, Lovász Lászlóval együttműködésben kidolgozott multifraktál hálózatgeneráló módszert. A cél itt minél nagyobb statisztikus hasonlóság elérése a kapott véletlen gráfok és a bemeneti hálózat között a gráf struktúrát kódoló multifraktál paramétereinek maximum likelihood módszereken alapuló optimalizálásával.

Mi a kutatás alapkérdése?
Ebben a részben írja le röviden, hogy mi a kutatás segítségével megválaszolni kívánt probléma, mi a kutatás kiinduló hipotézise, milyen kérdéseket válaszolnak meg a kísérletek.

A címkéző rendszerekkel kapcsolatban alaphipotézisünk az, hogy a felhasználók gondolkodása bizonyos mértékig hierarchikus. Ehhez köthetően a következő kérdésekre keressük a választ:
-Hogyan fedhetők fel a hierarchia jelei a címkéző rendszerek statisztikus tulajdonságaiban és miként építhetünk fel egy címke-ontológiát a címke-statisztikák alapján?
-Milyen függvények segítségével lehetne kvantitatívan mérni a kinyert ontológiák minőségét?
-A különböző ontológia kinyerő algoritmusok összehasonlításához miként lehet létrehozni egy kontrollálható, a címkéző rendszerekkel analóg sztochasztikus tesztrendszert?
A hierarchiával, csoportokkal és címkékkel kapcsolatban hipotézisünk az, hogy a csoportokhoz jó eséllyel lehet találni reprezentáns címkéket, melyek gyűjtőfogalomként vagy kulcsszóként összegzik a csoporttagok összesített címkefelhőjét. Ez a feltevés azon alapszik, hogy a csoportok egy magasabb szerveződési szintet képeznek a hálózat felépítésében, ezért a tagjaikon található címkék vélhetően sokkal szorosabb kapcsolatban vannak egymással, mint egy véletlenszerűen választott csúcshalmaz címkéi. Kapcsolódó kérdésünk:
-Mi a csoportszintű címkeválasztás optimális módja, mely egyfelől jól összegzi a csoporttagok címkéit, másfelől elősegíti a keresést a hálózatban?
A multifraktál hálózatgenerálóval kapcsolatos hipotézisünk az, hogy a gráf-struktúrát kódoló multifraktál paramétereit lehet optimalizálni arra, hogy a kapott véletlen gráfok statisztikus értelemben minél hasonlóbbak legyenek egy megadott bemeneti hálózathoz. Az idevágó kérdés a következő:
-Hogyan lehet hatékonyan optimalizálni a multifraktál paramétereket?

Mi a kutatás jelentősége?
Röviden írja le, milyen új perspektívát nyitnak az alapkutatásban az elért eredmények, milyen társadalmi hasznosíthatóságnak teremtik meg a tudományos alapját. Mutassa be, hogy a megpályázott kutatási területen lévő hazai és a nemzetközi versenytársaihoz képest melyek az egyediségei és erősségei a pályázatának!

A hierarchikus szerveződés egy általános jelenség, mely a természet és a társadalom számos komplex rendszerének sajátossága. Bár jelenlétét könnyű észlelni, a hierarchia (vagy hierarchikusság) mértékét nem triviális kvantitatívan mérni, emiatt az utóbbi időben az ilyen irányú kutatások nagy tudományos érdeklődést váltottak ki. Terveink szerint több érdekes, új szemponttal bővítjük a hierarchiával kapcsolatos kutatásokat.
A címke-hierarchiához (címke-ontológiákhoz) kötődő tervek számos új elméleti kihívást tartalmaznak, pl. a kinyert ontológiák minőségét mérő mennyiségek definiálása a címke statisztikák segítségével egy fokozottan nem triviális probléma. Másfelől, a címkéző rendszerek növekvő népszerűségének köszönhetően ez a kutatási irány nagyon aktuális és releváns a gyakorlati alkalmazások szempontjából is, hiszen egy megbízható címke-hierarchia pl. nagyban segítheti a keresést. Emellett számos online áruház is lehetővé teszi a termékek címkézését a címkéző rendszerekhez hasonló módon, ezért a várható eredmények relevánsak az ajánló rendszerek szempontjából is. Minthogy kulcsszavak és egyéb, a címkékhez hasonló metaadatok a legtöbb tudományos publikáción is megjelennek, ezen a téren elért előrelépések az új tudományos eredmények automatizált kategorizálását is segíthetik.
A hálózati csoportok szintén a tudományos figyelem központjában voltak az elmúlt néhány évben, a tervbe vett csoportcímkézési probléma vizsgálata egy új frontot nyit ezen a téren, a hierarchiához és a címkékhez szorosan kapcsolódva. Gyakorlati szempontból a csoport szintű címkék hasonló módon segíthetik a hálózatban a keresést, mint a címke ontológiák magasabb szintű elemei.
Végezetül a multifraktál hálózatgeneráló optimalizálása egy szintén fontos tudományos probléma, mely eleme a kutatási tervnek. Rugalmasságának köszönhetően ez a megközelítés már korábban is nagyon ígéretesnek bizonyult széles skálán változó tulajdonságú véletlen gráfok generálására. A módszer továbbfejlesztése potenciálisan egy olyan általános véletlen hálózat generáló eszközhöz juttat, melynél a gráf topológiáját egy hierarchikus struktúra kódolja.

A kutatás összefoglalója, célkitűzései laikusok számára
Ebben a fejezetben írja le a kutatás fő célkitűzéseit alapműveltséggel rendelkező laikusok számára. Ez az összefoglaló a döntéshozók, a média illetve az adófizetők tájékoztatása szempontjából különösen fontos az NKFI számára.

Komplex rendszerek hierarchikus szerveződését tervezzük vizsgálni új aspektusokból. Az elmúlt években az Interneten egyre népszerűbbé vált a szabad szavas címkézés az online áruházaktól (pl. Amazon) kezdve a pontosan erre a célra kifejlesztett címkéző platformokig (pl. Flickr). Szeretnénk egy átfogó keretrendszert kidolgozni az ilyen rendszerekben felbukkanó címkék általános- és speciális kategóriákból álló hierarchiába szervezéséhez a címkék statisztikus tulajdonságai alapján. Egy megbízható címke-hierarchia nagy gyakorlati jelentőséggel bírna, pl. jelentősen megkönnyítené a keresés tárgykörének szűkítését vagy bővítését, ami alapján ajánlásokat lehetne adni a felhasználók részére, és segítheti új objektumok automatikus bekategorizálást is.
Szintén a hierarchiához és a címkékhez kapcsolódnak a hálózati csoportok címkézésével kapcsolatos kutatási terveink is. A csoportok a csúcsokhoz képest egy magasabb szintet képviselnek a rendszer felépítésében, és egy igen intenzíven kutatott területét adják a komplex hálózatoknak. Célunk az optimális csoport szintű címkék kiválasztását segítő módszerek kifejlesztése, melyek egyfelől megfelelően összegzik a csoporttagok címkefelhőjét, másfelől segítik a keresést a hálózatban.
A hierarchia fontos szerepet tölt be a hálózati modellek területén is. Ehhez kapcsolódóan a multifraktál alapú hierarchikus véletlen-gráf generálóval kapcsolatos korábbi kutatásainkat tervezzük folytatni. Fő célkitűzésünk itt a modell optimalizálása adott bemeneti hálózathoz hasonló statisztikájú véletlen gráf generálására. Az így kapott gráfok ezután különféle hipotézisek tesztelésére vagy valódi hálózatok modelljeiként szolgálhatnak.
Summary
Summary of the research and its aims for experts
Describe the major aims of the research for experts.

We plan to study the hierarchical organisation in complex systems from new perspectives. Our primary research focus concerns the extension of our previous work on tagged networks to tagging systems, in which users can associate freely chosen words as tags to various objects (books, web-pages, photos, etc.) Although a predefined tag hierarchy is absent here, the way users think about objects presumably has some built in hierarchy, e.g., ``Puli'' is usually considered as a special case of ``dog''. Our plan is to establish a framework rooted in statistical physics for revealing this sort of hierarchy (ontology) between the tags. Beside heuristics we would also like to define a quantitative function measuring the quality of the obtained hierarchy based on tag statistics. Furthermore, we would also like to define a controllable computer generated benchmark system, on which the different ontology constructing algorithms could be tested. Along with testing on the to be developed benchmark system we plan to test our methods on real tagging systems as well.
Related to tagging and hierarchy we also plan to develop methods for choosing representative tags for communities in networks. This part of the research heavily relies on our former experience in community finding and will partly involve statistical methods from Natural Language Processing.
Finally, we plan the optimisation of the multifractal network generator introduced by our group in collaboration with L. Lovász. The goal here is to tune the parameters of the multifractal encoding of the network structure to yield random graphs similar to arbitrary chosen input network based on maximum likelihood techniques.

What is the major research question?
Describe here briefly the problem to be solved by the research, the starting hypothesis, and the questions addressed by the experiments.

Concerning the online tagging systems our primary hypothesis is that the way users think about objects presumably has some built in hierarchical aspects. Our research questions related to this are the following:
-How can we detect signs of this hierarchy in the statistical properties of tagging systems, and how can we construct an ontology for the tags based on their statistics?
-Is it possible to provide a quantitative measure for the quality of the obtained ontology?
-What are the basic principles for designing a controllable stochastic benchmark system analogous to the real tagging systems?
Related to hierarchy, tags and communities our hypothesis is that it is possible to find representative tags for network modules acting as super categories or key words for the cloud of tags on the community members. This assumption is based on the fact that communities provide a higher level of organisation in the system, thus, the tags on the members are much more likely to have a well defined common super category compared to randomly chosen nodes from the given network. Our related research question is the following:
-What is the optimal way for assigning tags to communities which best describe the cloud of tags on the members, and also help searching in the network?
Related to the multifractal network generator our hypothesis is that it is possible to optimise the multifractal encoding the structure of the generated random graph with respect to a given input network. The related research question is the following:
-What is the most efficient way of tuning the parameters of the generator in order to obtain random graphs statistically similar to a given input network?

What is the significance of the research?
Describe the new perspectives opened by the results achieved, including the scientific basics of potential societal applications. Please describe the unique strengths of your proposal in comparison to your domestic and international competitors in the given field.

Hierarchical organisation is a widespread feature in nature and in the society. Although easily perceived, it is difficult to quantify, and advances in the description and analysis of the emergence of hierarchy have received an intensively growing scientific interest recently. We plan to extend the directions of research in this field from various new perspectives.
The ontology extraction problem (or tag hierarchy construction problem) on the one hand has several interesting theoretical aspects, e.g., the definition of a quality function for the obtained ontology based on tag statistics is highly non-trivial. On the other hand, due to the increasing popularity of online tagging systems, this research has also great actuality and relevance for practical applications, e.g., a reliable hierarchy between the tags can seriously improve searching. Furthermore, many online stores and webshops offer the possibility of tagging their products in a similar fashion to tagging systems, thus, the expected results are likely to be relevant for recommendation systems as well. Since keywords and various other metadata analogous to tags appear on most scientific publications as well, advances in this field can also help automated categorisation of new scientific results.
Communities have been in the centre of network research in the last few years, the community tagging problem we plan to tackle opens a new front in this area, in a close relation with tagging and hierarchies. From the practical point of view, the community level tags can help searching in a similar fashion to higher levels tags in an ontology.
Finally, the optimisation of the multifractal network generator is yet another significant problem included in our research plan. This approach has already been proven to be very promising from the point of view of flexibility in generating random graphs with properties varying on a large scale. The further optimisation of the method has the potential for providing a general random graph generating tool with an underlying hierarchical structure.

Summary and aims of the research for the public
Describe here the major aims of the research for an audience with average background information. This summary is especially important for NKFI in order to inform decision-makers, media, and the taxpayers.

We plan to study the hierarchical organisation in complex systems from various new perspectives. In recent years, the voluntary tagging of items with free words has become a popular way of summarizing their most important aspects in a wide range of online platforms from web-stores (e.g., Amazon) to tagging systems (e.g., Flickr). We plan to develop a general framework for organising these tags into a hierarchy of general- and more specific subcategories based on their statistical properties. A reliable hierarchy between the tags has a great potential for practical applications, e.g., it can significantly help broadening or narrowing the scope of search in the system, give recommendation about yet unvisited objects to the user, or help categorization of newly appearing objects.
Another problem related to hierarchy and tags we plan to tackle is the tagging of communities in complex networks. Communities (also called as modules or clusters), provide a higher level of organisation compared to nodes and have been in the focus of research for the last few years. Our goal is to develop methods for choosing community tags which best describe the cloud of tags on the community members, and can also help searching in the network.
Hierarchy is a central concept in the field of network models as well. Relating to that we plan the continuation of our previous research concerning a general hierarchical random graph generator based on multifractals. Our main goal here is to optimize this model for generating random graphs statistically similar to a given input network. These graphs could be used to test hypotheses, or, treated as models of actual data.





 

Final report

 
Results in Hungarian
-Bevezettünk új címkehierarchia-kinyerő algoritmusokat, egy számítógéppel generálható tesztrendszert az ilyenfajta algoritmusok tesztelésére és egy hierarchiákra vonatkozó hasonlóságmértéket. -A címkehierarchia-kinyerő algoritmus segítségével a szerzői- és az adatbázis-készítői által generált kulcsszavak hierarchiáit hasonlítottuk össze a Web of Science-ben elérhető publikációk esetén: a hierarchiák teteje nagy hasonlóságot mutatott, míg az alsó szinteknél jelentős volt az eltérés. -Különböző online hírportálokból kinyert címkehierarchiák összehasonlítása megmutatta, hogy a címkézés szervezettségében jelentős eltérések vannak a különböző médiáknál. -A k-klikk perkoláció kritikus pontjánál modularitások tanulmányozásával igazoltuk a csoportkeresésnél használt optimális paraméterbeállítási szabályok helyességét. -Megmutattuk, hogy a tudományos publikációk hivatkozási hálózata univerzális hierarchikus tulajdonságokat mutat ha az egyes témáknak megfelelő részgráfokra bontjuk. -Egy új megközelítést javasoltunk tudományos folyóiratok rangsorolására az újságok hierarchiába rendezésével, ahol az újságokban megjelenő cikkek közti hivatkozások alapján egyrészt előállt egy irányítási hierarchia (mely az információ terjesztés szempontjából fontos), másrészt egy bennfoglalási hierarchia (mely a tudományterületek alapján ad egy automatikus rendszerezést).
Results in English
-We introduced novel algorithms for extracting tag hierarchies, together with a computer generated benchmark system for testing tag hierarchy extraction methods, and a similarity measure for comparing hierarchies. -Our tag hierarchy extraction framework was applied to both author given- and repository given keywords of publications in the Web of Science, and the obtained hierarchies showed large similarity at the top and a low similarity at the lower levels. -The comparison between tag hierarchies extracted between tags appearing in different online news portals revealed that tagging was organised to different degrees over the media. -Our studies of modularities at the critical point of k-clique percolation justified the usual criteria for choosing the optimal parameter setting during the community finding. -We showed that the directed citation network between scientific papers shows universal hierarchical features when broken into sub-networks corresponding to different scientific fields. -We proposed a new approach to quantifying journal impact by organising the scientific journals into both a flow hierarchy (relevant from the point of view of information spreading), and a nested hierarchy, (organising the journals according to the scientific fields), based on the citations between the publications appearing in the journals. -We developed a new hierarchy measure preferring trees over chains and stars based on random walks on the network.
Full text https://www.otka-palyazat.hu/download.php?type=zarobeszamolo&projektid=105447
Decision
Yes





 

List of publications

 
Czegel D, Palla G: Random walk hierarchy measure: What is more hierarchical, a chain, a tree or a star?, SCI REP 5, 17994, 2015
G. Tibély, P. Pollner, T. Vicsek, G. Palla: Extracting tag hierarchies, PLoS ONE 8, e84133, 2013
Mones, E., Pollner, P., Vicsek, T.: Universal hierarchical behavior of citation networks., J. Stat. Mech. 2014, P05023, 2014
Tibely G, Sousa-Rodrigues D, Pollner P, Palla G: Comparing the Hierarchy of Keywords in On-Line News Portals, PLOS ONE 11, e0165728, 2016
B. Tóth, T. Vicsek, G. Palla: Overlapping modularity at the critical point of k-clique percolation, Journal of Statistical Physics 151, 689-706, 2013
G. Tibély, P. Pollner, T. Vicsek, G. Palla: Extracting tag hierarchies, PLoS ONE, 2013
G. Palla, G. Tibély, E. Mones, P. Pollner, T. Vicsek,: Hierarchical networks of scientific journals, Palgrave Communications 1, 15016, 2015
E. Mones, P. Pollner, T. Vicsek: Universal hierarchical behavior of citation networks, JOURNAL OF STATISTICAL MECHANICS: THEORY AND EXPERIMENT 2014:(5) Paper P05023, 2014
D. Czégel, G. Palla: Random walk hierarchy measure: What is more hierarchical, a chain, a tree or a star?, http://arxiv.org/abs/1508.07732, 2015
Á Szántó-Várnagy, P. Pollner, T. Vicsek, I. J. Farkas: Scientometrics: Untangling the topics, NATIONAL SCIENCE REVIEW 1:(3) pp. 343-345, 2014
Tibély, G., Pollner, P., Palla, G.: Comparing the hierarchy of author given tags and repository given tags in a large document archive., The European Physical Journal Special Topics 225, 2025, 2016
Horváth, A., Páll, N., Molnár, K., Kováts, T., Surján, G., Vicsek, T., Pollner, P.: A nationwide study of the epidemiology of relapsing polychondritis., Clinical Epidemiology 8, 211--230, 2016
Szántó-Várangy, Á., Pollner, P., Farkas, I. J.: Measuring originality in knowledge networks., Lect. Notes Comput. Sc. 9197, 156799, 2015





 

Events of the project

 
2016-06-15 09:47:43
Résztvevők változása




Back »