کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
6871582 1440187 2018 40 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
The resistance perturbation distance: A metric for the analysis of dynamic networks
ترجمه فارسی عنوان
فاصله تحرک مقاومت: متریک برای تجزیه و تحلیل شبکه های پویا
ترجمه چکیده
برای تعیین تحول بنیادین شبکه های متغیر زمان و شناسایی رفتار غیر طبیعی، نیاز به یک مفهوم تفاوت زمانی است که تغییرات سازمانی قابل توجهی را بین دو لحظه متوالی درک می کند. در این کار، ما یک خانواده از فاصله ها را پیشنهاد می کنیم تا بتوانیم تغییرات ساختاری بر روی یک گراف در مقیاس های مختلف را تعیین کنیم: از مقیاس محلی که توسط همسایگان هر رأس تشکیل شده است، به بزرگترین مقیاس که ارتباط بین خوشه ها را تعیین می کند، یا جوامع رویکرد ما در تعریف یک فاصله واقعی، و نه صرفا یک مفهوم شباهت، نتیجه می شود. ما پیشنهاد می کنیم الگوریتم های تصادفی سریع (خطی در تعداد لبه ها) را که می توانند به سرعت یک تقریب را به ماتریس گراف محاسبه کنند. سهم سوم شامل یک الگوریتم سریع برای افزایش استحکام یک شبکه با بهینه کاهش شاخص کرچوف است. در نهایت ما چندین آزمایش بر روی نمودارهای مصنوعی و شبکه های واقعی انجام می دهیم و نشان می دهیم که می توانیم تغییرات پیکربندی را که به طور مستقیم به متغیرهای پنهان حاکم بر تکامل شبکه های پویا است، شناسایی کنیم.
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر نظریه محاسباتی و ریاضیات
چکیده انگلیسی
To quantify the fundamental evolution of time-varying networks, and detect abnormal behavior, one needs a notion of temporal difference that captures significant organizational changes between two successive instants. In this work, we propose a family of distances that can be tuned to quantify structural changes occurring on a graph at different scales: from the local scale formed by the neighbors of each vertex, to the largest scale that quantifies the connections between clusters, or communities. Our approach results in the definition of a true distance, and not merely a notion of similarity. We propose fast (linear in the number of edges) randomized algorithms that can quickly compute an approximation to the graph metric. The third contribution involves a fast algorithm to increase the robustness of a network by optimally decreasing the Kirchhoff index. Finally, we conduct several experiments on synthetic graphs and real networks, and we demonstrate that we can detect configurational changes that are directly related to the hidden variables governing the evolution of dynamic networks.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Applied Mathematics - Volume 236, 19 February 2018, Pages 347-386
نویسندگان
, ,