Cited By
View all- Araujo de Rezende Cde Carvalho Junior F(2018)MapReduce with Components for Processing Big Graphs2018 Symposium on High Performance Computing Systems (WSCAD)10.1109/WSCAD.2018.00026(108-115)Online publication date: Oct-2018
BLADYG: A Novel Block-Centric Framework for the Analysis of Large Dynamic Graphs
Pages 39 - 42
Abstract
Recently, distributed processing of large dynamic graphs has become very popular, especially in certain domains such as social network analysis, Web graph analysis and spatial network analysis. In this context, many distributed/parallel graph processing systems have been proposed, such as Pregel, GraphLab, and Trinity. These systems can be divided into two categories: (1) vertex-centric and (2) block-centric approaches. In vertex-centric approaches, each vertex corresponds to a process, and message are exchanged among vertices. In block-centric approaches, the unit of computation is a block, a connected subgraph of the graph, and message exchanges occur among blocks. In this paper, we are considering the issues of scale and dynamism in the case of block-centric approaches. We present BLADYG, a block-centric framework that addresses the issue of dynamism in large-scale graphs. We present an implementation of BLADYG on top of AKKA framework. We experimentally evaluate the performance of the proposed framework.
References
[1]
H. Aksu, M. Canim, Y.-C. Chang, I. Korpeoglu, and O. Ulusoy. Distributed k-core view materialization and maintenance for large dynamic graphs. Knowledge and Data Engineering, IEEE Transactions on, 26(10):2439--2452, Oct 2014.
[2]
J. I. Alvarez-Hamelin, A. Barrat, A. Vespignani, and et al. k-core decomposition of internet graphs: hierarchies, self-similarity and measurement biases. Networks and Heterogeneous Media, 3(2):371, 2008.
[3]
V. Batagelj and M. Zaversnik. Fast algorithms for determining (generalized) core groups in social networks. Advances in Data Analysis and Classification, 5(2):129--145, 2011.
[4]
C. Giatsidis, D. Thilikos, and M. Vazirgiannis. Evaluating cooperation in communities with the k-core structure. In Proc. of the Int. Conf. on Advances in Social Networks Analysis and Mining, July 2011.
[5]
J. Leskovec and A. Krevl. SNAP Datasets: Stanford large network dataset collection. http://snap.stanford.edu/data, June 2014.
[6]
R. Li, J. X. Yu, and R. Mao. Efficient core maintenance in large dynamic graphs. IEEE Trans. Knowl. Data Eng., 26(10):2453--2465, 2014.
[7]
Y. Low, D. Bickson, J. Gonzalez, and et al. Distributed graphlab: A framework for machine learning and data mining in the cloud. Proc. VLDB Endow., 5(8):716--727, Apr. 2012.
[8]
G. Malewicz, M. H. Austern, A. J. Bik, and et al. Pregel: A system for large-scale graph processing. In Proc. of the 2010 ACM SIGMOD Int. Conf. on Management of Data, pages 135--146. ACM, 2010.
[9]
A. Montresor, F. D. Pellegrini, and D. Miorandi. Distributed k-core decomposition. IEEE Trans. Parallel Distrib. Syst., 24(2):288--300, 2013.
[10]
R. Patuelli, A. Reggiani, P. Nijkamp, and F.-J. Bade. The evolution of the commuting network in Germany: Spatial and connectivity patterns. Journal of Transport and Land Use, 2(3), 2010.
[11]
A. Sala, L. Cao, C. Wilson, R. Zablit, H. Zheng, and B. Y. Zhao. Measurement-calibrated graph models for social network experiments. In Proc. of the 19th Int. Conf. on World Wide Web (WWW'10). ACM, 2010.
[12]
B. Shao, H. Wang, and Y. Li. Trinity: A distributed graph engine on a memory cloud. In Proc. of the Int. Conf. on Management of Data. ACM, 2013.
[13]
Y. Tian, A. Balmin, S. A. Corsten, and et al. From "think like a vertex" to "think like a graph". Proc. VLDB Endow., 7(3):193--204, 2013.
[14]
D. Wyatt. Akka Concurrency. Artima Inc., 2013.
[15]
Y. Xu, J. Cheng, A. W. Fu, and Y. Bu. Distributed maximal clique computation. In Proc. of the IEEE Int. Congress on Big Data, pages 160--167, 2014.
[16]
D. Yan, J. Cheng, Y. Lu, and W. Ng. Blogel: A block-centric framework for distributed computation on real-world graphs. Proc. VLDB Endow., 7(14):1981-1992, Oct. 2014.
Index Terms
- BLADYG: A Novel Block-Centric Framework for the Analysis of Large Dynamic Graphs
Recommendations
Distributed k-core decomposition and maintenance in large dynamic graphs
DEBS '16: Proceedings of the 10th ACM International Conference on Distributed and Event-based SystemsDistributed processing of large, dynamic graphs has recently received considerable attention, especially in domains such as the analytics of social networks, web graphs and spatial networks. k-core decomposition is one of the significant figures of ...
GraBi: Communication-Efficient and Workload-Balanced Partitioning for Bipartite Graphs
ICPP '20: Proceedings of the 49th International Conference on Parallel ProcessingMachine Learning and Data Mining (MLDM) applications, such as recommendation and topic modeling, generally represent their input data in bipartite graphs with two disjoint vertex-subsets connected only by edges between them. Despite the prevalence of ...
A fast method to exactly calculate the diameter of incremental disconnected graphs
The breadth of problems requiring graph analytics is growing rapidly. Diameter is one of the most important metrics of a graph. The diameter is important in both designing algorithms for graphs and understanding the nature and evolution of graphs. ...
Comments
Please enable JavaScript to view thecomments powered by Disqus.Information & Contributors
Information
Published In
May 2016
60 pages
ISBN:9781450343503
DOI:10.1145/2915516
- General Chairs:
- Toyotaro Suzumura,
- Dario Garcia-Gasulla,
- Program Chair:
- Miyuru Dayarathna
Copyright © 2016 ACM.
Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]
Sponsors
- University of Arizona: University of Arizona
- SIGARCH: ACM Special Interest Group on Computer Architecture
In-Cooperation
Publisher
Association for Computing Machinery
New York, NY, United States
Publication History
Published: 31 May 2016
Check for updates
Author Tags
Qualifiers
- Short-paper
Conference
HPDC'16
Sponsor:
- University of Arizona
- SIGARCH
HPDC'16: The 25th International Symposium on High-Performance Parallel and Distributed Computing
May 31, 2016
Kyoto, Japan
Acceptance Rates
HPGP '16 Paper Acceptance Rate 5 of 6 submissions, 83%;
Overall Acceptance Rate 5 of 6 submissions, 83%
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- View Citations1Total Citations
- 94Total Downloads
- Downloads (Last 12 months)1
- Downloads (Last 6 weeks)0
Reflects downloads up to 13 Nov 2024
Other Metrics
Citations
Cited By
View all- Araujo de Rezende Cde Carvalho Junior F(2018)MapReduce with Components for Processing Big Graphs2018 Symposium on High Performance Computing Systems (WSCAD)10.1109/WSCAD.2018.00026(108-115)Online publication date: Oct-2018
View Options
Get Access
Login options
Check if you have access through your login credentials or your institution to get full access on this article.
Sign in