Community Finding in Large Social Networks Through Problem Decomposition

Files in This Item:
 File SizeFormat
Downloaducd-csi-2008-4.pdf406.96 kBAdobe PDF
Title: Community Finding in Large Social Networks Through Problem Decomposition
Authors: Narasimhamurthy, AnandGreene, DerekHurley, Neil J.Cunningham, Pádraig
Permanent link: http://hdl.handle.net/10197/12369
Date: Aug-2008
Online since: 2021-07-30T13:41:55Z
Abstract: The identification of cohesive communities is a key process in social network analysis. However, the algorithms that are effective for finding communities do not scale well to very large problems, as their time complexity is worse than linear in the number of edges in the graph. This is an important issue for those interested in applying social network analysis techniques to very large networks, such as networks of mobile phone subscribers. In this respect the contributions of this report are two-fold. First we demonstrate these scaling issues using a prominent community-finding algorithm as a case study. We then show that a twostage process, whereby the network is first decomposed into manageable subnetworks using a multilevel graph partitioning procedure, is effective in finding communities in networks with more than 106 nodes.
Funding Details: Enterprise Ireland
Science Foundation Ireland
Type of material: Technical Report
Publisher: University College Dublin. School of Computer Science and Informatics
Series/Report no.: UCD CSI Technical Reports; ucd-csi-2008-4
Copyright (published version): 2008 the Authors
Keywords: Social network analysisScalabilityProblem decompositionSolution quality
Other versions: https://web.archive.org/web/20080226040105/http:/csiweb.ucd.ie/Research/TechnicalReports.html
Language: en
Status of Item: Not peer reviewed
This item is made available under a Creative Commons License: https://creativecommons.org/licenses/by-nc-nd/3.0/ie/
Appears in Collections:CASL Research Collection
Computer Science and Informatics Technical Reports

Show full item record

Page view(s)

107
Last Week
8
Last month
81
checked on Sep 20, 2021

Download(s)

10
checked on Sep 20, 2021

Google ScholarTM

Check


If you are a publisher or author and have copyright concerns for any item, please email research.repository@ucd.ie and the item will be withdrawn immediately. The author or person responsible for depositing the article will be contacted within one business day.