دانلود مقاله تشخیص جامعه در شبکه های بدون مقیاس: الگوریتم های تقریبی برای به حداکثر رساندن مدولاسیون
تعداد کلمات فایل انگلیسی:7270 کلمه 10 صفحه pdf
تعداد صفحات فایل ترجمه :36 صفحه word فونت 14 B Nazanin
تشخیص جامعه در شبکه های بدون مقیاس: الگوریتم های تقریبی برای به حداکثر رساندن مدولاسیون
چکیده
بسیاری از شبکه ها، بی تفاوت از عملکرد و دامنه خود، به یک معماری بدون مقیاس که در آن توزیع درجه تقریبا به دنبال یک قانون قدرت است، همگرا می شود. در همین حال، بسیاری از این شبکه های بدون مقیاس به طور طبیعی به جوامع گره های متصل انبوده تقسیم می شوند که به عنوان ساختار جامعه شناخته می شوند. پیدا کردن این ساختار جامعه یک موضوع اساسی، اما چالش برانگیز در علم شبکه است. از زمان پیشنهاد نیومن برای استفاده از مدولاسیون به عنوان اندازه گیری برای تعیین کمیت قدرت ساختار جامعه، بسیاری از روش های کارآمد که ساختار جامعه را بر اساس حداکثرسازی مدولاریته پیدا می کنند، پیشنهاد شده اند. با این حال، کمبود الگوریتم های تقریبی وجود دارد که مرزهای کیفیت قابل اثبات را برای مشکل فراهم می کنند. در این مقاله، الگوریتم تقریبی زمانی- چندجمله ای برای مسئله حداکثر سازی مدولاریته همراه با توجیه نظری آنها در زمینه شبکه های بدون مقیاس ارائه شده است. ما ثابت می کنیم که راه حل های الگوریتم های پیشنهادی، حتی در بدترین حالت، بهینه هستند به یک عامل ثابت برای شبکه های بدون مقیاس با هر دو لینک دو طرفه یا یک طرفه بهینه هستند. با وجودی که تمرکز ما در این کار، بر طراحی الگوریتم های تجربی خوب برای تشخیص ساختار جامعه نیست، آزمایش روی شبکه های دنیای واقعی نشان می دهد که الگوریتم پیشنهادی با الگوریتم حداکثر سازی مدولاریته پیشرفته قابل رقابت است.
کلمات کلیدی: علم شبکه، الگوریتم تقریبی، ساختار جامعه، مدولاریته، شبکه های اجتماعی
:Community Detection in Scale-Free Networks
Approximation Algorithms for
Maximizing Modularity
Thang N. Dinh and My T. Thai
Abstract—Many networks, indifferent of their function and scope, converge to a scale-free architecture in which the degree distribution approximately follows a power law. Meanwhile, many of those scale-free networks are found to be naturally divided into communities of densely connected nodes, known as community structure. Finding this community structure is a fundamental but challenging topic in network science. Since Newman’s suggestion of using modularity as a measure to qualify the strength of community structure, many efficient methods that find community structure based on maximizing modularity have been proposed. However, there is a lack of approximation algorithms that provide provable quality bounds for the problem. In this paper, we propose polynomial-time approximation algorithms for the modularity maximization problem together with their theoretical justifications in the context of scale-free networks. We prove that the solutions of the proposed algorithms, even in the worst-case, are optimal up to a constant factor for scale-free networks with either bidirectional or unidirectional links. Even though our focus in this work is not on designing another empirically good algorithms to detect community structure, experiments on real-world networks suggest that the proposed algorithm is competitive with the state-of-the-art modularity maximization algorithm.
Index Terms—Network science, approximation algorithm, community structure, modularity, social networks;
کد:13231
دانلود رایگان مقاله انگلیسی کامپیوتر : تشخیص جامعه در شبکه های بدون مقیاس: الگوریتم های تقریبی برای به حداکثر رساندن مدولاسیون
رمز فایل :www.downloadmaghaleh.com
دانلود مقاله دات کام 
توضیحات محصول
دانلود مقاله تشخیص جامعه در شبکه های بدون مقیاس: الگوریتم های تقریبی برای به حداکثر رساندن مدولاسیون
تعداد کلمات فایل انگلیسی:7270 کلمه 10 صفحه pdf
تعداد صفحات فایل ترجمه :36 صفحه word فونت 14 B Nazanin
تشخیص جامعه در شبکه های بدون مقیاس: الگوریتم های تقریبی برای به حداکثر رساندن مدولاسیون
چکیده
بسیاری از شبکه ها، بی تفاوت از عملکرد و دامنه خود، به یک معماری بدون مقیاس که در آن توزیع درجه تقریبا به دنبال یک قانون قدرت است، همگرا می شود. در همین حال، بسیاری از این شبکه های بدون مقیاس به طور طبیعی به جوامع گره های متصل انبوده تقسیم می شوند که به عنوان ساختار جامعه شناخته می شوند. پیدا کردن این ساختار جامعه یک موضوع اساسی، اما چالش برانگیز در علم شبکه است. از زمان پیشنهاد نیومن برای استفاده از مدولاسیون به عنوان اندازه گیری برای تعیین کمیت قدرت ساختار جامعه، بسیاری از روش های کارآمد که ساختار جامعه را بر اساس حداکثرسازی مدولاریته پیدا می کنند، پیشنهاد شده اند. با این حال، کمبود الگوریتم های تقریبی وجود دارد که مرزهای کیفیت قابل اثبات را برای مشکل فراهم می کنند. در این مقاله، الگوریتم تقریبی زمانی- چندجمله ای برای مسئله حداکثر سازی مدولاریته همراه با توجیه نظری آنها در زمینه شبکه های بدون مقیاس ارائه شده است. ما ثابت می کنیم که راه حل های الگوریتم های پیشنهادی، حتی در بدترین حالت، بهینه هستند به یک عامل ثابت برای شبکه های بدون مقیاس با هر دو لینک دو طرفه یا یک طرفه بهینه هستند. با وجودی که تمرکز ما در این کار، بر طراحی الگوریتم های تجربی خوب برای تشخیص ساختار جامعه نیست، آزمایش روی شبکه های دنیای واقعی نشان می دهد که الگوریتم پیشنهادی با الگوریتم حداکثر سازی مدولاریته پیشرفته قابل رقابت است.
کلمات کلیدی: علم شبکه، الگوریتم تقریبی، ساختار جامعه، مدولاریته، شبکه های اجتماعی
:Community Detection in Scale-Free Networks
Approximation Algorithms for
Maximizing Modularity
Thang N. Dinh and My T. Thai
Abstract—Many networks, indifferent of their function and scope, converge to a scale-free architecture in which the degree distribution approximately follows a power law. Meanwhile, many of those scale-free networks are found to be naturally divided into communities of densely connected nodes, known as community structure. Finding this community structure is a fundamental but challenging topic in network science. Since Newman’s suggestion of using modularity as a measure to qualify the strength of community structure, many efficient methods that find community structure based on maximizing modularity have been proposed. However, there is a lack of approximation algorithms that provide provable quality bounds for the problem. In this paper, we propose polynomial-time approximation algorithms for the modularity maximization problem together with their theoretical justifications in the context of scale-free networks. We prove that the solutions of the proposed algorithms, even in the worst-case, are optimal up to a constant factor for scale-free networks with either bidirectional or unidirectional links. Even though our focus in this work is not on designing another empirically good algorithms to detect community structure, experiments on real-world networks suggest that the proposed algorithm is competitive with the state-of-the-art modularity maximization algorithm.
Index Terms—Network science, approximation algorithm, community structure, modularity, social networks;
کد:13231
دانلود رایگان مقاله انگلیسی کامپیوتر : تشخیص جامعه در شبکه های بدون مقیاس: الگوریتم های تقریبی برای به حداکثر رساندن مدولاسیون
رمز فایل :www.downloadmaghaleh.com