The week's pick
Random Articles
Reseach Article
A Parallel Algorithm to Calculate the Costrank of a Network
| International Journal of Computer Applications |
| Foundation of Computer Science (FCS), NY, USA |
| Volume 44 - Number 3 |
| Year of Publication: 2012 |
| Authors: Thaier Hamid, Carsten Maple, Yong Yue |
10.5120/6243-8161
|
Thaier Hamid, Carsten Maple, Yong Yue . A Parallel Algorithm to Calculate the Costrank of a Network. International Journal of Computer Applications. 44, 3 ( April 2012), 17-22. DOI=10.5120/6243-8161
Abstract
We developed analogous parallel algorithms to implement CostRank for distributed memory parallel computers using multi processors. Our intent is to make CostRank calculations for the growing number of hosts in a fast and a scalable way. In the same way we intent to secure large scale networks that require fast and reliable computing to calculate the ranking of enormous graphs with thousands of vertices (states) and millions or arcs (links). In our proposed approach we focus on a parallel CostRank computational architecture on a cluster of PCs networked via Gigabit Ethernet LAN to evaluate the performance and scalability of our implementation. In particular, a partitioning of input data, graph files, and ranking vectors with load balancing technique can improve the runtime and scalability of large-scale parallel computations. An application case study of analogous Cost Rank computation is presented. Applying parallel environment models for one-dimensional sparse matrix partitioning on a modified research page, results in a significant reduction in communication overhead and in per-iteration runtime. We provide an analytical discussion of analogous algorithms performance in terms of I/O and synchronization cost, as well as of memory usage.
References
- T. H. Haveliwala. Topic-sensitive pagerank. Proc. of the 11th WWW Conf. , 2002
- S. D. Kamvar, T. H. Haveliwala, C. D. Manning, and G. H. Golub. Exploiting the block structure of the web for computing pagerank. Preprint, March 2003.
- T. H. Haveliwala. Efficient encodings for document ranking vectors. Technical report, Stanford University, November 2002.
- U. V. Catalyurek and C. Aykanat. Hypergraph-Partitioning-Based Decomposition for Parallel Sparse-Matrix Vector Multiplication. IEEE Transactions on Parallel and Distributed Systems, 10(7):673–693, 1999.
- Thaier Hamid and Carsten Maple, IJCA Special Issue on Network Security and Cryptography Number 1 2011, ISBN: 978-93-80865-66-7.
- U. V. Catalyurek and C. Aykanat. A Fine-grain Hypergraph Model for 2D Decomposition. In Proc. 15th IEEE International Parallel and Distributed Processing Symposium, San Francisco, CA, 2001.
- G. Karypis, K. Schloegel, and V. Kumar. ParMeTiS: Parallel Graph Partitioning and Sparse Matrix Ordering Library, Version 3. 0. University of Minnesota, 2002.
- B. U¸car and C. Aykanat. Encapsulating multiple communication cost metrics in artitioning sparse rectangular matrices for parallel matrix–vector multiples. SIAM Journal on Scientific Computing, 25(6):1837–1859, 2004.
- A. Arasu, J. Novak, A. Tomkins, and J. Tomlin. Pagerank computation and the structure of the web: Experiments and algorithms. Proc. of the 11th WWW Conf. ,2002. Poster Track.
- K. Bharat, B. W. Chang, and M. Henzinger. Who links to whom: Mining linkage between web sites. Proc. of the IEEE Conf. on Data Mining, November 2001.
- Aleksandar Trifunovic. Parallel Algorithms for Hyper graph Partitioning. Ph. D. thesis, University of London 2006.
- Y. Chen, Q. Gan, and T. Suel. I/O-efficient techniques for computing pagerank. Proc. of the 11th ACM CIKM Conf. , 2002.
- S. Chien, C. Dwork anf R. Kumar, and D. Sivakumar. Towards exploting link evolution. Workshop on Algorithms and Models for the Web Graph, 2001.
- Russell Power, Jinyang Li. Piccolo Building fast, distributed program with partitioned tables.
- Arnon Rungsawang and Bundit Manaskasemsak, PageRank Computation Using PC Cluster, Dongarra, D. Laforenza, S. Orlando 2003.
Index Terms
Keywords