Individual and Collective Graph Mining: Principles, Algorithms, and Applications

گراف‌ها به طور طبیعی اطلاعاتی از پیوندهای بین صفحات وب، ارتباطات در شبکه‌های ایمیل، تا ارتباطات بین نورون‌های مغز ما را نشان می‌دهند. این نمودارها اغلب میلیاردها گره و تعامل بین آنها را در بر می گیرند. در درون این سیل داده های به هم پیوسته، چگونه می توانیم مهم ترین ساختارها را پیدا کرده و آنها را خلاصه کنیم؟ چگونه می توانیم آنها را به طور موثر تجسم کنیم؟ چگونه می‌توانیم ناهنجاری‌هایی را که نشان‌دهنده رویدادهای مهم هستند، مانند حمله به یک سیستم کامپیوتری، تشکیل بیماری در مغز انسان، یا سقوط یک شرکت، تشخیص دهیم؟

این کتاب الگوریتم‌های کشف مقیاس‌پذیر و اصولی را ارائه می‌کند که ترکیبی از آنها هستند. جهانی بودن با محلی بودن برای درک یک یا چند نمودار. علاوه بر روش‌شناسی الگوریتمی سریع، ما همچنین ایده‌ها و مدل‌های نظری نمودار و کاربردهای دنیای واقعی را در دو حوزه اصلی ارائه می‌کنیم:

•کاوی نمودار فردی: ما نشان می‌دهیم که چگونه می‌توان یک نمودار را به صورت تفسیری خلاصه کرد و با شناسایی آن ساختارهای نمودار مهم آن ما خلاصه‌سازی را با استنتاج تکمیل می‌کنیم، که اطلاعات مربوط به چند موجودیت (به‌دست‌آمده از طریق خلاصه‌سازی یا روش‌های دیگر) و ساختار شبکه را برای یادگیری مؤثر و مؤثر اطلاعات در مورد موجودیت‌های ناشناخته به کار می‌گیرد.

•کاوی نمودار جمعی: ما دامنه را گسترش می‌دهیم. ایده خلاصه کردن گراف های فردی به نمودارهای در حال تکامل زمان، و نشان می دهد که چگونه می توان الگوهای زمانی را به صورت مقیاس پذیر کشف کرد. جدای از خلاصه، ما ادعا می کنیم که شباهت گراف اغلب مشکل اساسی در بسیاری از برنامه ها است که در آن نمودارهای متعدد رخ می دهند (مانند تشخیص ناهنجاری زمانی، کشف الگوهای رفتاری)، و الگوریتم های اصولی و مقیاس پذیر را برای تراز کردن شبکه ها و اندازه گیری شباهت آنها ارائه می کنیم. .

روش هایی که در این کتاب ارائه می کنیم از تکنیک هایی از حوزه های مختلف مانند جبر ماتریس، نظریه گراف، بهینه سازی، نظریه اطلاعات، یادگیری ماشین، امور مالی و علوم اجتماعی برای حل مسائل دنیای واقعی استفاده می کنند. . ما کاربردهای الگوریتم های کاوش خود را در مجموعه داده های عظیم ارائه می کنیم، از جمله یک نمودار وب با 6.6 میلیارد یال، یک نمودار توییتر با 1.8 میلیارد یال، نمودارهای مغزی با حداکثر 90 میلیون یال، همکاری، شبکه های همتا به همتا، گزارش های مرورگر و همه. شامل میلیون ها کاربر و تعامل است.

Graphs naturally represent information ranging from links between web pages, to communication in email networks, to connections between neurons in our brains. These graphs often span billions of nodes and interactions between them. Within this deluge of interconnected data, how can we find the most important structures and summarize them? How can we efficiently visualize them? How can we detect anomalies that indicate critical events, such as an attack on a computer system, disease formation in the human brain, or the fall of a company?

This book presents scalable, principled discovery algorithms that combine globality with locality to make sense of one or more graphs. In addition to fast algorithmic methodologies, we also contribute graph-theoretical ideas and models, and real-world applications in two main areas:

•Individual Graph Mining: We show how to interpretably summarize a single graph by identifying its important graph structures. We complement summarization with inference, which leverages information about few entities (obtained via summarization or other methods) and the network structure to efficiently and effectively learn information about the unknown entities.

•Collective Graph Mining: We extend the idea of individual-graph summarization to time-evolving graphs, and show how to scalably discover temporal patterns. Apart from summarization, we claim that graph similarity is often the underlying problem in a host of applications where multiple graphs occur (e.g., temporal anomaly detection, discovery of behavioral patterns), and we present principled, scalable algorithms for aligning networks and measuring their similarity.

The methods that we present in this book leverage techniques from diverse areas, such as matrix algebra, graph theory, optimization, information theory, machine learning, finance, and social science, to solve real-world problems. We present applications of our exploration algorithms to massive datasets, including a Web graph of 6.6 billion edges, a Twitter graph of 1.8 billion edges, brain graphs with up to 90 million edges, collaboration, peer-to-peer networks, browser logs, all spanning millions of users and interactions.