شخصی سازی رتبه خوشه بندی : گراف الگوریتم خوشه بندی بر اساس Random Walk
گراف خوشه بندی بخشی اساسی در روش های بسیاری بوده است و در نتیجه دقت بر آن اثر قابل توجهی در بسیاری از برنامه های کاربردی دارد. علاوه بر این، رشد نمایی گراف های دنیای واقعی مانند شبکه های اجتماعی، شبکه های بیولوژیکی و مدارهای الکتریکی خواستار الگوریتم های خوشه بندی با زمان نزدیک به خطی و پیچیدگی فضا هستند. در این مقاله ما شخصی سازی رتبه خوشه بندی (PPC) را پیشنهاد کردیم که خوشه اصلی جهت آشکار سازی خوشه های گراف داده شده ،خاصیت اکتشافی Random Walk را به کار می گیرد.ما Random Walk و Modularity را به دقت ترکیب کردیم و به طوری کارآمد خوشه های یک گراف نشان می دهد. PPC ، یک الگوریتم بالا به پایین است ،به طوری که می تواند خوشه های اصلی یک گراف را دقیق تر از روش های نزدیک به زمان خطی دیگر که عمدتا از پایین به بالا هستند ،را نشان دهد. همچنین یک سلسله مراتب از خوشه هایی که در بسیاری از برنامه های کاربردی مفید است را ارائه می دهد. PPC ،دارای یک زمان خطی و پیچیدگی مکانی است ونسبت به بسیاری از الگوریتم های خوشه بندی در دسترس، در بسیاری از مجموعه داده ها برتر بوده است. علاوه بر این، رویکرد بالا به پایین آن ،یک راه حل انعطاف پذیر برای مشکلات خوشه بندی با شرایط مختلف می سازد.
معرفی
گراف ها نقش مهمی در مدل سازی سیستم بازی می کنند. در تعداد زیادی از حوزه ها مانند زیست شناسی، شبکه های اجتماعی و مهندسی برق، گراف ها برای مدل سیستم های دنیای واقعی استفاده می شود. بنابراین پیشنهاد دقیق تر و سریعتر الگوریتم های گراف می تواند محققان را در بسیاری از حوزه ها در اخذ نتایج بهتر کمک کند. یکی از مهمترین مسائل در مورد گرافها این است که چگونه خوشه ها (جوامع) را تشخیص دهیم. خوشه ها گراف ها ی فرعی ای هستند که بسیار از داخل متصل هستند و بین اتصال آنها پایین است. مشکل خوشه بندی می تواند به عنوان یک مسئله بهینه سازی دیده می شود و برای آن بسیاری توابع هزینه (یا هدف) ارائه شده است. در این مقاله ما خوشه ها را با توجه به مدل ارتباطات مردم پیدا کردیم. بنابراین در برنامه های کاربردی مانند شبکه های اجتماعی به نتایج بسیار خوبی دست خواهد یافت از آنجا که تابع هزینه خوشه ، سازگار با منطق شکل گیری جامعه است هر چند به نتایج خوبی برای انواع دیگر گراف ها دست یافته است. در بخش ۴ دقیق تر توضیح داده خواهد شد.
از سوی دیگر، با توجه به رشد انفجاری از گراف دنیای واقعی مانند شبکه های اجتماعی، الگوریتم های کلاسیک دیگر کافی نیست ، از آنجایی که آنها معمولا دارای فضای بالا و یا پیچیدگی زمانی هستند. بنابراین توسعه ی الگوریتم های جدید که به صورت خطی در اندازه گراف (به عنوان مثال تعداد رئوس و تعداد لبه ها) می تواند دامنه ای از مشکلات قابل حل در یک مدت زمان معقول را گسترش دهد.
در این مقاله روش جدیدی برای خوشه بندی است که ترکیبی از Random Walk وModularity برای نمایش خوشه اصلی یک گراف بدون جهت، هر دو مدل وزن دار و بدون وزن را معرفی می کنیم . دلیل اینکه Random Walk مناسب برای خوشه بندی می باشد این است که راه رفتن تصادفی محدود به طول تمایل دارد به ماندن داخل یک خوشه با احتمال بالا به جای انتقال به خوشه های مختلف. چرا که اتصال درونی یک خوشه خوب است به طور قابل توجهی بزرگتر از درون اتصال به آن است. بنابراین اگر ما بسیاری ازشروع های Random Walk را با یک راس تنها در داخل یک خوشه که دقیقا تعریف شده است انجام دهیم بسیاری از آنها احتمالا در آن خوشه به دام خواهد افتاد. بنابراین، رئوس در دیگر خوشه ها بطور قابل توجهی باردیدهای کمتری از دیگر رئوس در همان خوشه خواهد داشت.
بنابراین پیاده روی های تصادفی با طول محدود را از یک راس شروع کردیم و رئوس را بر طبق تعداد بازدیدهایی که برای به دست آوردن فهرستی از رئوس مرتب شده بر اساس شباهت خوشه خود به راس شروع مرتب سازی کردیم. سپس، اگر ما نقطه برش مناسب در لیست پیدا کنیم، گراف را می توان به دو زیر گراف از هم جدا تقسیم کرد. بنابراین با انجام این کار به صورت بازگشتی تا رسیدن به شرایط خاص یک سلسله مراتب از خوشه ساخته می شود.
در این مقاله، رویکرد جدیدی را با خوشه بندی ارائه می دهیم که مسیرهای تصادفی و Modularity را جهت نمایش خوشه بندی درونی یک گراف یک جهتی، سنجیده شده و سنجیده نشده را ترکیب می کرد. دلیلی که چرا مسیرهای تصادفی برای خوشه بندی مناسب است آن است که مسیر تصادفی با طول محدود داخل خوشه ای با قابلیت احتمال تا حدی بالاتر از انتقال به خوشه متفاوت قرار می گیردزیرا که ارتباط درونی خوشه خوب، به نحوی مشخص و ………بیشتر از ارتباط بینش است.بنابراین اگر چندین مسیرتصادفی باشد با شروع از یک راس خاص در محدوده خوشه بطور دقیق تعریف شده عموما” از آنها داشته باشیم، احتمالا” در آن خوشه گیر می کنیم. راس ها در دیگر خوشه ها بطور قابل توجهی بازدیدهای کمتر از راس ها در خوشه مناسب را خواهد داشت.بنابراین چندین مسیر تصادفی با طول محدود را از راس شروع می کنیم و راس را برطبق مسیر اگر نقطه برش مناسب در لیست را پیدا کنیم، گراف می توانست در دو گراف فرعی جز بندی شود که سلسه مراتب خوشه ها انجام می شود.
روش مطرح شده خوشه بندی رتبه صفحه شخصی شده مان ( ppc) را بیان می کنیم و نشان می دهیم که ویژگی های خیلی خوب دارد و در جنبه های مختلف به الگوریتم های کنونی برتر است . نشان خواهیم داد که ppc پیچیدگی زمانی خطی دارد که بدین معنی است که برای گراف های خیلی بزرگ قابل قیاس است. همچنین نشان خواهیم داد که ppc در مفهومی درست است که نه تنها از مجاورهای فوری راس بلکه همچنین راس هایی با فواصل بالاتر استفاده نمی کند و بنابراین دیدگاهش از قبیل چندین دیدگاه دیگر محلی نیست. از سوی دیگر ، برخلاف اکثر الگوریتم های خوشه بندی گراف سریع، ppc الگوریتم بالا – پایین است بنابراین می تواند دیدگاه کل نگرانه ای از گراف داشته باشد و ساختارهای جهانی پیدا می کند که برای مشاهده کننده انسانی بهتر قابل مشاهده است و … بنابراین منجر به خوشه های منطقی تر می شود. در حقیقت، ppc تمایل دارد تا خوشه های با دانه درشت را پیدا کند که از دیدگاه مشاهده کننده انسانی و نه خوشه های با دانه ریز که مشخص و بارز است که فقط بطور محلی قابل درک است. همچنین رویکرد بالا-پایین آن را برای خوشه های تکراری مناسب می سازد. کاربر می تواند نتیجه هر مرحله جز بندی را مشاهده کند و عمیق تر حرکت کند و اگر مطلوب باشد، بزرگنمایی یا کوچک نمایی کند که پیچیدگی زمان الگوریتم را کاهش می دهد. زمانیکه فقط چند مرحله برای کاربر کافی و موثر باشد.
Personalized PageRank Clustering: A graph clustering algorithm based on random walks
Abstract
Graph clustering has been an essential part in many methods and thus its accuracy has a significant effect on many applications. In addition, exponential growth of real-world graphs such as social networks, biological networks and electrical circuits demands clustering algorithms with nearly-linear time and space complexity. In this paper we propose Personalized PageRank Clustering (PPC) that employs the inherent cluster exploratory property of random walks to reveal the clusters of a given graph. We combine random walks and modularity to precisely and efficiently reveal the clusters of a graph. PPC is a top-down algorithm so it can reveal inherent clusters of a graph more accurately than other nearly-linear approaches that are mainly bottom-up. It also gives a hierarchy of clusters that is useful in many applications. PPC has a linear time and space complexity and has been superior to most of the available clustering algorithms on many datasets. Furthermore, its top-down approach makes it a flexible solution for clustering problems with different requirements.
لینک مقاله اصلی:
https://www.sciencedirect.com/science/article/pii/S0378437113006316
لطفاً براي ارسال دیدگاه، ابتدا وارد حساب كاربري خود بشويد