Repository logo
  • Log In
    New user? Click here to register.Have you forgotten your password?
University College Dublin
  • Colleges & Schools
  • Statistics
  • All of DSpace
  • Log In
    New user? Click here to register.Have you forgotten your password?
  1. Home
  2. College of Science
  3. School of Computer Science
  4. Computer Science and Informatics Technical Reports
  5. Community Finding in Large Social Networks Through Problem Decomposition
 
  • Details
Options

Community Finding in Large Social Networks Through Problem Decomposition

File(s)
FileDescriptionSizeFormat
Download ucd-csi-2008-4.pdf406.96 KB
Author(s)
Narasimhamurthy, Anand 
Greene, Derek 
Hurley, Neil J. 
Cunningham, Pádraig 
Uri
http://hdl.handle.net/10197/12369
Date Issued
August 2008
Date Available
30T13:41:55Z July 2021
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.
Sponsorship
Enterprise Ireland
Science Foundation Ireland
Type of Material
Technical Report
Publisher
University College Dublin. School of Computer Science and Informatics
Series
UCD CSI Technical Reports
ucd-csi-2008-4
Copyright (Published Version)
2008 the Authors
Keywords
  • Social network analys...

  • Scalability

  • Problem decomposition...

  • Solution quality

Web versions
https://web.archive.org/web/20080226040105/http:/csiweb.ucd.ie/Research/TechnicalReports.html
Language
English
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/
Owning collection
Computer Science and Informatics Technical Reports
Views
333
Acquisition Date
Feb 1, 2023
View Details
Downloads
24
Last Week
4
Last Month
5
Acquisition Date
Feb 1, 2023
View Details
google-scholar
University College Dublin Research Repository UCD
The Library, University College Dublin, Belfield, Dublin 4
Phone: +353 (0)1 716 7583
Fax: +353 (0)1 283 7667
Email: mailto:research.repository@ucd.ie
Guide: http://libguides.ucd.ie/rru

Built with DSpace-CRIS software - Extension maintained and optimized by 4Science

  • Cookie settings
  • Privacy policy
  • End User Agreement