علوم رایانش و فناوری اطلاعات

الگوریتم موازی برای کاوش زیرگراف های منسجم در گراف های حجیم

نویسندگان

دانشکده مهندسی و علوم کامپیوتر، دانشگاه شهید بهشتی، تهران

چکیده

یافتن زیرگراف های منسجم در بسیاری از کاربردها از جمله موتورهای جستجو، شبکه های اجتماعی و شبکه های بیولوژی جایگاه ویژه ای دارد. در این بین، زیرگراف K-Truss به دلیل سادگی و کاربردهایی مانند یافتن نقاط پرچگال و ترسیم گراف کاربرد اهمیت دارد. با توجه به حجم زیاد گراف ها، توسعه ی الگوریتم های موازی برای افزایش سرعت در پاسخدهی نیازی اساسی است. برای این منظور، در این مقاله یک الگوریتم موازی برای کاوش زیرگراف های منسجم در گراف های حجیم در 2 فاز ارائه شده است؛ در فاز اول، ابتدا با یک الگوریتم موازی مثلث های گراف یافت می شوند و خروجی ها در یک ساختار جدید با نام رأسهای مثلثی برای نگهداری مجموعه رأسهایی که با هر یال تشکیل یک مثلث می دهند، تولید می شود. در فاز دوم، در یک حلقه به صورت موازی یالهای نامعتبر به تدریج از مجموعه یالهای موجود حذف میگردند تا زمانی که هیچ یالی که خصوصیت K-Truss را نقض می کند، پیدا نشود. کارایی روش پیشنهادی در مقایسه با دیگر روش ها و مقیاس پذیری آن، با انجام آزمایش هایی بر روی یک ماشین 12 هستهای با استفاده از مجموعه گرافهای استاندارد نشان داده شده است.

کلیدواژه‌ها

  • [1] S. Koujaku, I. Takigawa, M. Kudo, and H. Imai, "Dense core model for cohesive subgraph discovery," Social Networks, vol. 44, pp. 143-152, 2016.
  • [2] L. Qin, R. H. Li, L. Chang, and C. Zhang, "August. Locally densest subgraph discovery," Proc. 21th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, pp. 965-974, 2015.
  • [3] A. E. Sariyuce, C. Seshadhri, A. Pinar, and U. V. Catalyurek, "May. Finding the hierarchy of dense subgraphs using nucleus decompositions," Proc. 24th International Conference on World Wide Web, pp. 927-937, 2015.
  • [4] R. D. Luce, "Connectivity and generalized cliques in sociometric group structure", Psychometrika, vol. 15, no. 2, pp.169-190, 1950.
  • [5] R. J. Mokken, "Cliques, clubs and clans," Quality & Quantity, vol. 13, no. 2, pp.161-173, 1979.
  • [6] S. B. Seidman, and B. L. Foster, "A graph‐theoretic generalization of the clique concept*," Journal of Mathematical sociology, vol. 6, no. 1, pp.139-154, 1978.
  • [7] S. B. Seidman, "Network structure and minimum degree," Social networks, vol. 5, no. 3, pp. 269-287, 1983.
  • [8] J. Cohen, "Trusses: Cohesive subgraphs for social network analysis," National Security Agency Technical Report, p.16. 2008.
  • [9] F. Zhao, A. K Tung, "Large scale cohesive subgraphs discovery for social network visual analysis," Proc. VLDB Endowment. vol. 6, no. 2, VLDB Endowment, 2012.
  • [10] A. E. Sariyüce, and A. Pinar, "Fast hierarchy construction for dense subgraphs,” Proc. VLDB Endowment, vol. 10, no. 3, pp. 97-108, 2016.
  • [11] U. Redmond, H. Martin, and C. Pádraig, "Mining dense structures to uncover anomalous behaviour in financial network data," Modeling and mining ubiquitous social media, pp. 60-76, 2012.
  • [12] M. G. Rossi, and V. Michalis, "Exploring Network Centralities in Spreading Processes," International Symposium on Web AlGorithms (iSWAG). 2016.
  • [13] M. G. Rossi, D. M. Fragkiskos, and V. Michalis, "Locating influential nodes in complex networks," Scientific reports 6, (2016).
  • [14] M. G. Rossi, D. M. Fragkiskos, and V. Michalis, "Spread it good, spread it fast: Identification of influential nodes in social networks," Proc. 24th International Conference on World Wide Web, ACM, 2015.
  • [15] R. Bredereck, C. Komusiewicz, S. Kratsch, H. Molter, R. Niedermeier, and M. Sorge, “Assessing the computational complexity of multi-layer subgraph detection,” in International Conference on Algorithms and Complexity. Springer, 2017, pp. 128–139.
  • [16] X. Huang, L. V. Lakshmanan, J. X. Yu, and H. Cheng, “Approximate closest community search in networks,” Proceedings of the VLDB Endowment, vol. 9, no. 4, pp. 276–287, 2015.
  • [17] X. Huang, "Querying k-truss community in large and dynamic graphs," Proc. ACM SIGMOD international conference on Management of data. ACM, 2014.
  • [18] M. Alemi, H. Haghighi, and S. Shahrivari, "CCFinder: using Spark to find clustering coefficient in big graphs," The Journal of Supercomputing, pp. 1-28, 2017.
  • [19] J. Wang, and J. Cheng, "Truss decomposition in massive networks," Proc. VLDB Endowment, vol. 5. no.9, pp.812-823, 2012.
  • [20] Z. Zhaonian, and R. Zhu, "Truss decomposition of uncertain graphs," Knowledge and Information Systems, vol. 50, no. 1, pp. 197-230, 2017.
  • [21] R. A. Rossi, "Fast triangle core decomposition for mining large graphs," Proc. Pacific-Asia Conference on Knowledge Discovery and Data Mining, pp. 310-322, 2014.
  • [22] P. L. Chen, C. K. Chou, and M. S. Chen, "Distributed algorithms for k-truss decomposition," Proc. In Big Data (Big Data), 2014 IEEE International Conference on, pp. 471-480, 2014.
  • [23] Y. Shao, L. Chen, and B. Cui, "Efficient cohesive subgraphs detection in parallel," Proc. the 2014 ACM SIGMOD International Conference on Management of Data, pp. 613-624, 2014.
  • [24] J. Cohen, "Graph twiddling in a MapReduce world," Computing in Science & Engineering, vol. 11, no. 4, pp.29-41, 2009.
  • [25] J. Dean, S. Ghemawat, "MapReduce: simplified data processing on large clusters" Communications of the ACM, vol. 51, no. 1, pp.107-113, 2008.
  • [26] T. White, Hadoop: The definitive guide. O"Reilly Media, Inc., 2012.
  • [27] L. Quick, P. Wilkinson, and D. Hardcastle, "Using Pregel-like large scale graph processing frameworks for social network analysis," Proc. the 2012 International Conference on Advances in Social Networks Analysis and Mining, pp. 457-463, 2012.
  • [28] G. Malewicz, M. H. Austern, A. J. Bik, J. C. Dehnert, I. Horn, N. Leiser, and G. Czajkowski, "Pregel: a system for large-scale graph processing," Proc. the 2010 ACM SIGMOD International Conference on Management of data, pp. 135-146, 2010.
  • [29] SNAP: Stanford Network Analysis Project, http://snap.stanford.edu, June 2017.
  • [30] Network Repository, http://networkrepository.com, June 2017.
علوم رایانش و فناوری اطلاعات
دوره 16، شماره 2
پاییز و زمستان
آذر 1397