Analysis of the Semi-synchronous Approach to Large-scale Parallel Community Finding

Files in This Item:
File Description SizeFormat 
insight_publication.pdf268.86 kBAdobe PDFDownload
Title: Analysis of the Semi-synchronous Approach to Large-scale Parallel Community Finding
Authors: Duriakova, Erika
Hurley, Neil J.
Ajwani, Deepak
Sala, Alessandra
Permanent link:
Date: Oct-2014
Abstract: Community-finding in graphs is the process of identifying highly cohesive vertex subsets. Recently the vertex-centric approach has been found effective for scalable graph processing and is implemented in systems such as Graph Lab and Pregel. In the vertex-centric approach, the analysis is decomposed into a set of local computations at each vertex of the graph, with results propagated to neighbours along the vertexs edges. Many community finding algorithms area menable to this approach as they are based on the optimisation of an objective through a process of iterative local update (ILU), in which vertices are successively moved to the community of one of their neighbours in order to achieve the highest local gain in the quality of the objective. The sequential processing of such iterative algorithms generally benefits from an asynchronous approach, where a vertex update uses the most recent state as generated by the previous update of vertices in its neighbourhood. When vertices are distributed over a parallel machine, the asynchronous approach can encounter race conditions that impact on its performance and destroy the consistency of the results. Alternatively,a semi-synchronous approach ensures that only non-conflicting vertices are updated simultaneously. In this paper we study the semi-synchronous approach to ILU algorithms for community finding on social networks. Because of the heavy-tailed vertex distribution, the order inwhich vertex updates are applied in asynchronous ILU can greatly impact both convergence time and quality of the found communities. We study the impact of ordering on the distributed label propagation and modularity maximisation algorithms implemented on a shared-memory multicore architecture.We demonstrate that the semi-synchronous ILU approach is competitive in time and quality with the asynchronous approach, while allowing the analyst to maintain consistent control over update ordering. Thus, our implementation results in a more robust and predictable performance and provides control over the order in which the node labels are updated, which is crucial to obtaining the correct trade-off between running time and quality of communities on many graph classes.
Funding Details: Science Foundation Ireland
Type of material: Conference Publication
Publisher: ACM
Copyright (published version): 2014 ACM
Keywords: Machine Learning & StatisticsIterative local updateParallel graph algorithmsCommunity detection algorithmsSemi-synchronous Graph Algorithms
DOI: 10.1145/2660460.2660474
Language: en
Status of Item: Peer reviewed
Conference Details: ACM Conference on Online Social Network Analysis, Dublin Ireland,1-2 October, 2014
Appears in Collections:Insight Research Collection

Show full item record

Citations 50

Last Week
Last month
checked on Oct 11, 2018

Google ScholarTM



This item is available under the Attribution-NonCommercial-NoDerivs 3.0 Ireland. No item may be reproduced for commercial purposes. For other possible restrictions on use please refer to the publisher's URL where this is made available, or to notes contained in the item itself. Other terms may apply.