داده‌کاوی گراف ۲۰۲۲
Graph Mining 2022

وب چگونه به نظر می‌رسد؟ چگونه می‌توان الگوها، جوامع و نقاط پرت را در یک شبکه‌ی اجتماعی پیدا کرد؟ کدام گره‌ها در یک شبکه از همه مهم‌تر و مرکزی‌تر هستند؟ این‌ها پرسش‌هایی هستند که انگیزه بخش این اثرند. شبکه‌ها و گراف‌ها در زمینه‌های گوناگون و متنوعی ظاهر می‌شوند؛ برای مثال در شبکه‌های اجتماعی، شبکه‌های ارتباطی کامپیوتری (تشخیص نفوذ، مدیریت ترافیک)، شبکه‌های تعامل پروتئین-پروتئین در زیست‌شناسی، گراف‌های دو بخشی سند-متن در بازیابی متن، گراف‌های شخص-حساب در تشخیص تقلب مالی و غیره. در این اثر، ابتدا به فهرستی از الگوهای شگفت‌انگیزی می‌پردازیم که گراف‌های واقعی معمولاً از آن‌ها پیروی می‌کنند. سپس، فهرستی مفصل از مولدهایی ارائه می‌دهیم که سعی دارند این الگوها را منعکس کنند. مولدها مهم هستند، زیرا می‌توانند به سناریوهای “چه می‌شود اگر”، برون‌یابی‌ها و ناشناس‌سازی کمک کنند. در ادامه، لیستی از ابزارهای قدرتمند برای تحلیل گراف، و به طور خاص روش‌های طیفی (تجزیه مقادیر منفرد (SVD))، تانسورها، و مطالعات موردی مانند الگوریتم معروف “پیج‌رنک” و الگوریتم “HITS” برای رتبه‌بندی نتایج جستجوی وب ارائه می‌کنیم. در نهایت، با بررسی اجمالی ابزارها و مشاهدات از زمینه‌های مرتبط مانند جامعه‌شناسی، که دیدگاه‌های مکمل ارائه می‌دهند، نتیجه‌گیری می‌کنیم.

فهرست مطالب: مقدمه / الگوها در گراف‌های ایستا / الگوها در گراف‌های در حال تحول / الگوها در گراف‌های وزن‌دار / بحث: ساختار گراف‌های خاص / بحث: قوانین توانی و انحرافات / خلاصه الگوها / مولدهای گراف / پیوست ترجیحی و انواع آن / ترکیب اطلاعات جغرافیایی / RMat / تولید گراف با ضرب کرونکر / خلاصه و راهنمای کاربردی / SVD، گام‌های تصادفی و تانسورها / تانسورها / تشخیص اجتماع / انتشار نفوذ/ویروس و ایمن‌سازی / مطالعات موردی / شبکه‌های اجتماعی / سایر آثار مرتبط / نتیجه‌گیری

What does the Web look like? How can we find patterns, communities, outliers, in a social network? Which are the most central nodes in a network? These are the questions that motivate this work. Networks and graphs appear in many diverse settings, for example in social networks, computer-communication networks (intrusion detection, traffic management), protein-protein interaction networks in biology, document-text bipartite graphs in text retrieval, person-account graphs in financial fraud detection, and others. In this work, first we list several surprising patterns that real graphs tend to follow. Then we give a detailed list of generators that try to mirror these patterns. Generators are important, because they can help with “what if” scenarios, extrapolations, and anonymization. Then we provide a list of powerful tools for graph analysis, and specifically spectral methods (Singular Value Decomposition (SVD)), tensors, and case studies like the famous “pageRank” algorithm and the “HITS” algorithm for ranking web search results. Finally, we conclude with a survey of tools and observations from related fields like sociology, which provide complementary viewpoints. Table of Contents: Introduction / Patterns in Static Graphs / Patterns in Evolving Graphs / Patterns in Weighted Graphs / Discussion: The Structure of Specific Graphs / Discussion: Power Laws and Deviations / Summary of Patterns / Graph Generators / Preferential Attachment and Variants / Incorporating Geographical Information / The RMat / Graph Generation by Kronecker Multiplication / Summary and Practitioner’s Guide / SVD, Random Walks, and Tensors / Tensors / Community Detection / Influence/Virus Propagation and Immunization / Case Studies / Social Networks / Other Related Work / Conclusions