University of Victoria (Canada)
Influential community discovery in massive social networks using a consumer-grade machine
Abstract
dc:description.abstractGraphs have become very crucial as they can represent a wide variety of systems in different areas. One interesting structure called community in graphs has attracted considerable attention from both academia and industry. Community detection is meaningful, but typically hard in arbitrary networks. A lot of research has been done based on structural information, but we would like to find communities which are not only cohesive but also influential or important. A k-influential community model based on k-core provided by Li, Qin, Yu, and Mao is helpful to discover these cohesive and important communities. They organize the problem as finding top-r most important communities in a given graph. In this thesis, our goal is to detect top-r most important communities using efficient and memory-saving algorithms running on a consumer-grade machine. We analyze two existing algorithms, then propose multiple new efficient algorithms for this problem. To test their performance, we conduct extensive experiments on some real-world graph datasets. Experimental results show that our algorithms are able to compute top-r most important communities within a very reasonable amount of time and space in a consumer-grade machine.
Degree
thesis:*- Level thesis:degree_level
- Master of Science M.Sc.
- Department thesis:degree_department
- Department of Computer Science
- Year dc:date.issued
- 2017
Author and committee
dc:creator, dc:contributor.*- Author dc:creator
-
- Chen, Shu
- Advisor dc:contributor.supervisor
-
- Thomo, Alex
Subjects
dc:subject × 2Rights
dc:rights- Statement dc:rights
-
- Available to the World Wide Web
- Language dc:language.iso
- en, English
Identifiers
dc:identifier.*- Handle dc:identifier.uri
- http://hdl.handle.net/1828/8367