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

چکیده

Graph embedding approaches attempt to project graphs into geometric entities, i.e, manifolds. The idea is that the geometric properties of the projected manifolds are helpful in the inference of graph properties. However, if the choice of the embedding manifold is incorrectly performed, it can lead to incorrect geometric inference. In this paper, we argue that the classical embedding techniques cannot lead to correct geometric interpretation as they miss the curvature at each point, of manifold. We advocate that for doing correct geometric interpretation the embedding of graph should be done over regular constant curvature manifolds. To this end, we present an embedding approach, the discrete Ricci flow graph embedding (dRfge) based on the discrete Ricci flow that adapts the distance between nodes in a graph so that the graph can be embedded onto a constant curvature manifold that is homogeneous and isotropic, i.e., all directions are equivalent and distances comparable, resulting in correct geometric interpretations. A major contribution of this paper is that for the first time, we prove the convergence of discrete Ricci flow to a constant curvature and stable distance metrics over the edges. A drawback of using the discrete Ricci flow is the high computational complexity that prevented its usage in large-scale graph analysis. Another contribution of this paper is a new algorithmic solution that makes it feasible to calculate the Ricci flow for graphs of up to 50k nodes, and beyond. The intuitions behind the discrete Ricci flow make it possible to obtain new insights into the structure of large-scale graphs. We demonstrate this through a case study on analyzing the internet connectivity structure between countries at the BGP level.

چکیده به فارسی (ترجمه ماشینی)

رویکردهای تعبیه شده نمودار تلاش می کنند تا نمودارها را به موجودات هندسی ، یعنی منیفولدها بپردازند.ایده این است که خصوصیات هندسی منیفولد های پیش بینی شده در استنباط خصوصیات نمودار مفید است.با این حال ، اگر انتخاب منیفولد تعبیه به طور نادرست انجام شود ، می تواند منجر به استنباط هندسی نادرست شود.در این مقاله ، ما استدلال می کنیم که تکنیک های تعبیه کلاسیک نمی توانند به تفسیر هندسی منجر شوند زیرا آنها انحنای در هر نقطه ، از منیفولد را از دست می دهند.ما از این طرفداری می کنیم که برای انجام تفسیر صحیح هندسی ، تعبیه نمودار باید بر روی منیفولدهای انحنای ثابت منظم انجام شود.برای این منظور ، ما یک رویکرد تعبیه شده را ارائه می دهیم ، نمودار گسسته جریان Ricci (DRFGE) بر اساس جریان Ricci گسسته که فاصله بین گره ها را در یک نمودار سازگار می کند ، به طوری که نمودار می تواند بر روی یک انحراف ثابت که همگن و همگن است تعبیه کنید.ایزوتروپیک ، یعنی همه جهت ها معادل و مسافت قابل مقایسه هستند و در نتیجه تفسیرهای هندسی صحیح ایجاد می شود.سهم عمده این مقاله این است که برای اولین بار ، ما همگرایی جریان گسسته Ricci را به یک انحنای ثابت و معیارهای فاصله پایدار بر روی لبه ها اثبات می کنیم.اشکال در استفاده از جریان گسسته Ricci ، پیچیدگی محاسباتی بالا است که از استفاده از آن در تجزیه و تحلیل نمودار در مقیاس بزرگ جلوگیری می کند.سهم دیگر این مقاله یک راه حل الگوریتمی جدید است که محاسبه جریان Ricci برای نمودارهای گره های حداکثر 50k و فراتر از آن امکان پذیر است.شهودهای موجود در جریان گسسته Ricci امکان دستیابی به بینش های جدید در ساختار نمودارهای در مقیاس بزرگ را فراهم می کند.ما این را از طریق یک مطالعه موردی در مورد تجزیه و تحلیل ساختار اتصال اینترنت بین کشورها در سطح BGP نشان می دهیم.