Crawling and Detecting Community Structure in Online Social Networks Using Local Information

Abstract : As Online Social Networks (OSNs) become an intensive subject of research for example in computer science, networking, social sciences etc., a growing need for valid and useful datasets is present. The time taken to crawl the network is however introducing a bias which should be minimized. Usual ways of addressing this problem are sampling based on the nodes (users) ids in the network or crawling the network until one “feels” a sufficient amount of data has been obtained.In this paper we introduce a new way of directing the crawling procedure to selectively obtain communities of the network. Thus, a researcher is able to obtain those users belonging to the same community and rapidly begin with the evaluation. As all users involved in the same community are crawled first, the bias introduced by the time taken to crawl the network and the evolution of the network itself is less.Our presented technique is also detecting communities during runtime. We compare our method called Mutual Friend Crawling (MFC) to the standard methods Breadth First Search (BFS) and Depth First Search (DFS) and different community detection algorithms. The presented results are very promising as our method takes only linear runtime but is detecting equal structures as modularity based community detection algorithms.
Type de document :
Communication dans un congrès
Robert Bestak; Lukas Kencl; Li Erran Li; Joerg Widmer; Hao Yin. 11th International Networking Conference (NETWORKING), May 2012, Prague, Czech Republic. Springer, Lecture Notes in Computer Science, LNCS-7289 (Part I), pp.56-67, 2012, NETWORKING 2012. 〈10.1007/978-3-642-30045-5_5〉
Liste complète des métadonnées

Littérature citée [18 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/hal-01531140
Contributeur : Hal Ifip <>
Soumis le : jeudi 1 juin 2017 - 11:35:12
Dernière modification le : samedi 18 novembre 2017 - 18:16:02
Document(s) archivé(s) le : mercredi 6 septembre 2017 - 18:24:19

Fichier

978-3-642-30045-5_5_Chapter.pd...
Fichiers produits par l'(les) auteur(s)

Licence


Distributed under a Creative Commons Paternité 4.0 International License

Identifiants

Citation

Norbert Blenn, Christian Doerr, Bas Kester, Piet Mieghem. Crawling and Detecting Community Structure in Online Social Networks Using Local Information. Robert Bestak; Lukas Kencl; Li Erran Li; Joerg Widmer; Hao Yin. 11th International Networking Conference (NETWORKING), May 2012, Prague, Czech Republic. Springer, Lecture Notes in Computer Science, LNCS-7289 (Part I), pp.56-67, 2012, NETWORKING 2012. 〈10.1007/978-3-642-30045-5_5〉. 〈hal-01531140〉

Partager

Métriques

Consultations de la notice

16

Téléchargements de fichiers

23