در گراف‌های نامعین ۲۰۲۲
On Uncertain Graphs 2022

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

Large-scale, highly interconnected networks, which are often modeled as graphs, pervade both our society and the natural world around us. Uncertainty, on the other hand, is inherent in the underlying data due to a variety of reasons, such as noisy measurements, lack of precise information needs, inference and prediction models, or explicit manipulation, e.g., for privacy purposes. Therefore, uncertain, or probabilistic, graphs are increasingly used to represent noisy linked data in many emerging application scenarios, and they have recently become a hot topic in the database and data mining communities. Many classical algorithms such as reachability and shortest path queries become #P-complete and, thus, more expensive over uncertain graphs. Moreover, various complex queries and analytics are also emerging over uncertain networks, such as pattern matching, information diffusion, and influence maximization queries. In this book, we discuss the sources of uncertain graphs and their applications, uncertainty modeling, as well as the complexities and algorithmic advances on uncertain graphs processing in the context of both classical and emerging graph queries and analytics. We emphasize the current challenges and highlight some future research directions.