Sie befinden Sich nicht im Netzwerk der Universität Paderborn. Der Zugriff auf elektronische Ressourcen ist gegebenenfalls nur via VPN oder Shibboleth (DFN-AAI) möglich. mehr Informationen...
X10-based distributed and parallel betweenness centrality and its application to social analytics
Ist Teil von
20th Annual International Conference on High Performance Computing, 2013, p.109-118
Ort / Verlag
IEEE
Erscheinungsjahr
2013
Quelle
IEEE Electronic Library (IEL)
Beschreibungen/Notizen
Betweenness centrality is a measure that determines the relative importance of a vertex (or an edge) within a graph based on shortest paths. Recently, large-scale graphs have emerged in many different domains, as social networks, road networks, protein interaction networks, etc., and they are too large to fit into the memory of a single SMP. The algorithm proposed by Edmonds et al. [1] is capable of running on distributed memory systems. However, the algorithm does not expose intra-node parallelism. In this paper we investigated the inter- and intra-node parallelism of computing betweenness centrality on distributed memory systems. We developed the implementation based on the algorithm proposed by Edmonds et al. using X10 programming language [2]. We further improved the performance of the implementation by optimizing the network transport of the X10 runtime. We thoroughly evaluated the performance of our implementation on synthetic graphs of various scales against the existing implementation of Edmonds' algorithm from PBGL. We estimated the betweenness centrality of the huge Twitter networks [3] and found that its distribution follows a power law.