Abstract

Adjacency matrix is an effective technique used to represent a graph or a Social network comprising of large number of vertices and edges. The intent is of this paper is to optimize the graph storage and mapping without using a large adjacency matrix to represent a large graph. A special data structure Treap, a combination of binary search tree and heaps has been used as a replacement to a large adjacency matrix. It has been experimentally evaluated that the proposed approach significantly improves the space occupied by adjacency matrix and helps the graph to grow dynamically without affecting the current data structure.

References

• J. B. Shearer and R. J. McEliece. 1977: "There is no Mac Williams identity for convolutional codes"; IEEE Trans. Inform. Theory, IT-23:775-776.
• Bernard Elspas and James Turner. 1970: "Graphs with circulant adjacency matrices", 297
• A. Cohen and V. Lefebvre. 1988: "Optimization of storage mappings for graphs" Technical Report 1998/46, PRiSM, U. of Versailles.
• H. Orsila, E. Salminen, M. H¨annik¨ainen, T. D. H¨am¨al¨ainen. 2007: "Optimal Subset Mapping And Convergence Evaluation of Mapping Algorithms for Distributing Task Graphs on Multiprocessor"; SoC, Symposium on SoC.
• Chris Lattner: "Heap Data Structure Analysis and Optimization ", Ph. D. Thesis
• R. W. Irving and L. Love. 2003: "The suffix binary search tree and suffix AVL tree"; J. Discrete Algorithms, 1(5-6):387-408.
• G. D. Forney and M. D. Trott. 2004: "The Dynamics of Group Codes: Dual Abelian Group Codes and Systems"; IEEE Trans. Inform. Theory, IT-50:2935-2965.
• A. A. Nanavati, S. Gurumurthy, G. Das, D. Chakraborty, K. Dasgupta, S. Mukherjee, A. Joshi. 2006: "On the structural properties of massive telecom call graphs: findings and implications"; In CIKM '06: Proceedings of the 15th ACM international conference on Information and knowledge management, New York, NY, USA, ACM, 435–444
• M. Newman, A. -L. Barabasi, D. J. Watts. 2006: "The Structure and Dynamics of Networks"
• G. Pike. 2002; "Reordering and Storage Optimizations for graphs"; PhD thesis, University of California, Berkeley.
• Frank O. 1981; "A Survey of Statistical Methods for Graph Analysis. Sociological Methodology", 110-155.
• Brewer, D. D. , Webster, C. M. . 1999; "Forgetting of friends and its effects on measuring friendship networks. Social Networks" 21, 361–373.
• Pattison, P. E. , Robins, G. L. 2002; "Neighbourhood-based models for social networks. Sociological Methodology" 32, 301–337.
• Watts, D. J. 1999; "Small Worlds: The Dynamics of Networks between Order and Randomness"; Princeton University Press, Princeton, NJ.
• Handcock, M. S. , Hunter, D. R. , Butts, C. T. , Goodreau, S. M. , Morris, M. 2008. Statnet: "Software Tools for the Representation, Visualization, Analysis and Simulation of Network Data"; Journal of Statistical Software 24 (1), URL, http://www. jstatsoft. org/v24/i01.
• A. Cohen. 1999; "Parallelization via constrained storage mapping optimization";
• A. Cohen and V. Lefebvre. 1988; "Optimization of storage mappings for parallel programs"; Technical Report 1998/46, PRiSM, U. of Versailles.
• P. Feautrier. 2001; "The use of farkas lemma in memory optimization".
• A. W. Lim, S. -W. 2001; "Liao, and M. S. Lam. Blocking and array contraction across arbitrarily nested loops using affine partitioning"; In Proceedings of the eighth ACM SIGPLAN symposium on Principles and practices of parallel programming, pages 103-112, ACM Press.
• W. Thies, F. Vivien, J. Sheldon, and S. Amarasinghe. 2001; "A unified framework for schedule and storage optimization"; In Proceedings of the ACM SIGPLAN 2001 Conference on Programming Language Design and Implementation, pages 232-242, ACM Press.
• Blelloch, Guy E, Reid-Miller, Margaret, (1998), "Fast set operations using Treaps", Proc. 10th ACM Symp. Parallel Algorithms and Architectures (SPAA 1998), New York, NY, USA: ACM, pp. 16–26.
• Martinez, Conrado, Roura, Salvador. 1997, "Randomized binary search trees", Journal of the ACM 45 (2): 288–323
• R. Seidel and C. R. Aragon. 1996; "Randomized search trees"; Algorithmica, 16:464-497.
• D. D. Sleator and R. E. Tarjan. 1985; "Self-adjusting binary trees"; Journal of the Association for Computing Machinery, 32(3):652-686.