Detection of network communities with memory-biased random walk algorithms

Autor:	Lev Muchnik, Uri Hershberg, Mesut Yucel
Rok vydání:	2016
Předmět:	Computational Mathematics Control and Optimization Computer Networks and Communications Computer science Applied Mathematics 0103 physical sciences Management Science and Operations Research 010306 general physics Random walk 01 natural sciences Algorithm 010305 fluids & plasmas
Zdroj:	Journal of Complex Networks. :cnw007
ISSN:	2051-1329 2051-1310
Popis:	Community structure and its detection in complex networks has been the subject of many studies in the recent years. Towards this goal, we have created a novel approach based on the analysis of the motion of a memory-biased random walker, i.e. an entity that traverses the network with some tendency to follow or avoid pathways it has previously traversed. We found that the walker tends to remain inside communities, that is, subsets of the network nodes which are more connected to each other, rather than to the rest of the network. Based on this trait of the MBRW we developed a method to detect communities and tested its performance on a range of networks with different levels of community structure. In all tested cases, the method proved to be at least as effective as Girvan-Newman or Infomap while outperforming them when communities were less well defined.
Databáze:	OpenAIRE
Externí odkaz:	https://explore.openaire.eu/search/publication?articleId=doi_dedup___::f2d367d3ee74c1ccca7b9a744d811968 https://doi.org/10.1093/comnet/cnw007 Zobrazit plný text záznamu