ترجمه مقاله الگوریتم های موازی سریع برای شباهت و تطبیق گراف

قیمت خرید این محصول

۳۹,۰۰۰ تومان

دانلود رایگان نمونه دانلود مقاله انگلیسی

عنوان فارسی

الگوریتم های موازی سریع برای شباهت و تطبیق گراف

عنوان انگلیسی

Fast Parallel Algorithms for Graph Similarity and Matching

صفحات مقاله فارسی

29

صفحات مقاله انگلیسی

28

سال انتشار

2012

فرمت مقاله انگلیسی

PDF

فرمت ترجمه مقاله

ورد تایپ شده

رفرنس

دارد

کد محصول

4983

وضعیت ترجمه عناوین تصاویر و جداول

ترجمه شده است

وضعیت ترجمه متون داخل تصاویر و جداول

ترجمه نشده است

وضعیت فرمولها و محاسبات در فایل ترجمه

به صورت عکس، درج شده است

رشته های مرتبط با این مقاله

مهندسی کامپیوتر، مهندسی فناوری اطلاعات و ریاضی

گرایش های مرتبط با این مقاله

مهندسی الگوریتم و محاسبات، مهندسی نرم افزار، سامانه های شبکه ای و ریاضی کاربردی

مجله

گزارش های علوم فنی کامپیوتر

دانشگاه

گروه ریاضی و علوم کامپیوتری، دانشگاه بازل، سوئیس

کلمات کلیدی

هم ترازی نمودار، شباهت راس، تطبیق موازی، الگوریتم مزایده

۰.۰ (بدون امتیاز)

امتیاز دهید

فهرست مطالب

چکیده
1- مقدمه و انگیزه
2- نتایج مرتبط
2-1 محاسبه شباهت های گراف
2-1-1 کاربردهای شباهت گراف
2-2 الگوریتم های انطباق وزنی در گراف های دو بخشی
3- الگوریتم سریالی برای محاسبات ماتریس شباهت وانطباق مبتنی بر مزایده
3-1 اصطلاحات و مقدمات اولیه
3-2 تجزیه شباهت شبکه (NSD)
3-3 انطباق وزنی دو بخشی مبتنی بر مزایده
3-4 اقدامات کیفی برای انطباق
4- ایجاد یک فرمولاسیون انطباق گراف موازی منسجم
4-1 موازی سازی NSD
4-2 انطباق وزنی مبتنی بر مزایده موازی
4-2-1 مقیاس گذاری ε
4-3 استراتژی پراکنده سازی موازی
4-4 پیچیدگی رویکرد یکپارچه
5- نتایج تجربی
5-1 بر قرار کردن و محیط تجربی
5-2 نتایج با پراکنده سازی
5-3 نتایج بدون پراکنده سازی
5-4 ارزیابی کیفیت
6- نتیجه گیری و کارهای آینده

نمونه چکیده متن اصلی انگلیسی

Abstract

With widespread availability of graph-structured data from sources ranging from social networks to biochemical processes, there is increasing need for efficient and effective graph analyses techniques. Graphs with millions of vertices and beyond are commonplace, necessitating both efficient serial algorithms, as well as scalable parallel formulations. This paper addresses the problem of global graph alignment on supercomputer-class clusters. Given two graphs (or two instances of the same graph), we define graph alignment as a mapping of each vertex in the first graph to a unique vertex in the second graph so as to optimize a given similarity-based cost function1 . Graph alignment is typically implemented in two steps – in the first step, a similarity matrix is computed. Entries in the matrix quantify similarity of node pairs, one chosen from each graph. In the second step, similar vertices are extracted through a bipartite matching algorithm applied to the similarity matrix. Using a state of the art serial algorithm for similarity matrix computation called Network Similarity Decomposition (NSD), we derive corresponding parallel formulations. Coupling this parallel similarity algorithm with a parallel auction-based bipartite matching technique, we derive a complete graph matching pipeline that is highly efficient and scalable. We validate the performance of our integrated approach on a large, supercomputer-class cluster and diverse graph instances (including Protein Interaction (PPI) networks, Web graphs, and Wikipedia link structures). Experimental results demonstrate that our algorithms scale to large machine configurations and problem instances.

نمونه چکیده ترجمه متن فارسی

چکیده
با دسترسی گسترده به داده های ساخت یافته گراف (رسم) از منابعی اعم از شبکه های اجتماعی تا فرآیندهای بیوشیمیایی، نیاز روز افزونی به تکنیک های آنالیز گراف کارآمد و موثر وجود دارد. گراف هایی با میلیونها راس و فراتر از آن متداول هستند و مستلزم الگوریتم های سریالی کارآمد، و همچنین فرمولاسیون موازی مقیاس پذیر میباشند. این مقاله به بیان مسئله تنظیم گراف سراسری در خوشه های کلاس ابر رایانه میپردازد. تطبیق دو گراف را به صورت نگاشت هر راس در گراف اول به راس منحصر به فردی در گراف دوم به منظور بهینه سازی هزینه مبتنی بر شباهت مورد نظر تعریف میکنیم. تراز نمودار معمولا در دو مرحله اجرا میشود - در مرحله اول، یک ماتریس شباهت محاسبه میگردد. اقلام درون ماتریس مشابهت جفت گره ها را تعیین کمیت و واجد شرای میکند، یک مورد از هر نمودار انتخاب شده است. در مرحله دوم، رئوس مشابه از طریق یک الگوریتم تطابق دو بخشی اعمال شده بر ماتریس شباهت استخراج شده است. با استفاده از تکنولوژی جدید الگوریتم سریال برای محاسبه ماتریس شباهت با نام تجزیه شباهت شبکه (NSD) مافرمولاسیون موازی متناظر را استنباط میکنیم. جفت کردن این الگوریتم شباهت موازی با روش تطابق دو بخشی مبتنی بر مزایده ، به خط لوله انطباق گراف مقیاس پذیر و کارا دست پیدا خواهیم کرد. ما عملکرد راهکار یکپارچه خود بر خوشه کلاس ابر رایانه های بزرگ و نمونه گراف های متنوع (از جمله شبکه های پروتئین اینتراکشن (PPI) ، وب گراف ها، و سازه های لینک ویکیپدیا) را تصدیق میکینم. نتایج تجربی نشان می دهد که الگوریتم های ما در پیکر بندی های دستگاه بزرگ و نمونه های مسئله مقیاس پذیر است.

برچسب‌ها: دانلود رایگان مقالات انگلیسی مهندسی فناوری اطلاعات IT، دانلود رایگان مقالات انگلیسی مهندسی کامپیوتر، دانلود رایگان مقالات انگلیسی ریاضی و آمار