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

Title

Author

Blenn, N.
Doerr, C.
Van Kester, B.
Van Mieghem, P.

Faculty

Electrical Engineering, Mathematics and Computer Science

Department

Network Architectures and Services Group (NAS)

Abstract

As Online Social Networks (OSNs) become an intensive sub- ject of research for example in computer science, networking, social sci- ences 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 su_cient 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 _rst, 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 di_erent community detection algorithms. The presented re- sults are very promising as our method takes only linear runtime but is detecting equal structures as modularity based community detection algorithms.

Subject

social networks
community detection
crawling

To reference this document use:

http://resolver.tudelft.nl/uuid:61624ff0-d637-497a-9bf1-355638b63c7e

DOI

https://doi.org/10.1007/978-3-642-30045-5_5

Publisher

Springer

ISBN

978-3-642-30045-5

Source

Proceedings 11th International IFIP TC 6 Networking Conference, Part 1, Praag, Czech Republic, 21-25 May 2012