نمایش مبدأ برای کپی کردن در شبکه‌ها

{{علوم شبکه}}   

'''روش کپی کردن''' (به [[زبان انگلیسی|انگلیسی]]: Copying Mechanism) فرآیندی است که در نتیجۀ آن، یک [[شبکه بی‌مقیاس|شبکه‌‌ بی‌مقیاس]] با استفاده از فرآیندی مکرر که در آن گره‌ها با جهش از گره‌های موجود کپی می‌شوند، ساخته شده و رشد می‌کند. در مدل عمومی آن، یک شبکۀ اولیۀ در حال رشد داده می‌شود و در هر مرحلۀ زمانی، یک گره جدید با درجۀ مشخص k (تعداد یال خروجی رأس جدید) به شبکه اضافه می‌شود. در قدم بعدی یک گره از شبکه به طور تصادفی انتخاب شده و گره جدید، اتصالات گره انتخاب‌شده را تقلید می‌کند و در نتیجۀ آن همسایه‌های مشترکی  با گره انتخاب‌شده خواهد داشت. <ref name="kogias">{{یادکرد کتاب|عنوان=Node Copying Models|عنوان کتاب=Networks, An Introduction|سال=2010|پیوند=https://www.google.com/books/edition/Networks/LrFaU4XCsUoC?hl=en&gbpv=0|نام=Mark|نام خانوادگی=Newman|صفحه=472|ویرایش=دوم}}</ref>

== ریشه‌ها ==
[[جان کلینبرگ]] و هم‌کارانش این مدل را برای توضیح شبکۀ ارجاعات مقالات و [[شبکه جهانی وب]] پیشنهاد کردند.<ref>{{یادکرد ژورنال|نام۱=Jon M.|نام خانوادگی۱=Kleinberg|نام۲=Ravi|نام خانوادگی۲=Kumar|نام۳=Prabhakar|نام خانوادگی۳=Raghavan|نام۴=Sridhar|نام خانوادگی۴=Rajagopalan|نام۵=Andrew S.|نام خانوادگی۵=Tomkins|سال=1999|عنوان=The Web as a Graph: Measurements, Models, and Methods}}</ref> از جمله دلایل ارائۀ این مدل برای این شبکه‌ها موارد زیر هستند:

* برخی از نویسندگان صفحات وب، به یک موضوع جالب اما جدید بین صفحات خاصی توجه می‌کنند و به صفحاتی که این اشتراک را دارند پیوند می‌دهند. صفحات ایجاد شده با این انگیزه، با انتخاب تصادفی از بین صفحات موجود مدل‌سازی می‌شوند.
* بیشتر نویسندگان به موضوعات خاصی که قبلاً ارائه شده‌اند علاقه‌مند هستند و پیوندهایی به صفحات مربوط به این موضوعات را جمع‌آوری می‌کنند. صفحات ایجاد شده به این روش را می‌توان با کپی کردن گره‌ها مدل‌سازی کرد.
* نویسندگان یک مقاله ممکن است به سادگی کل (یا بخشی از) ارجاعات یک مقالۀ مرتبط (با مقالۀ خود) را در ارجاعات مقالۀ خود کپی کنند، زیرا نویسندگان ممکن است با تعداد کمی مقالۀ مرتبط آشنا باشند و بقیۀ مقالات ارجاعی را به سادگی از مقالات مشابه تقلید کنند.<ref name="kogias">{{یادکرد کتاب|عنوان=Node Copying Models|عنوان کتاب=Networks, An Introduction|سال=2010|پیوند=https://www.google.com/books/edition/Networks/LrFaU4XCsUoC?hl=en&gbpv=0|نام=Mark|نام خانوادگی=Newman|صفحه=472|ویرایش=دوم}}</ref><ref>{{یادکرد ژورنال|نام۱=P. L.|نام خانوادگی۱=Krapivsky|نام۲=S.|نام خانوادگی۲=Redner|سال=2005|عنوان=Network Growth by Copying|سری=71|ژورنال=Phys. Rev.}}</ref>

== توضیح مدل ==
در حالت کلی، مدل‌های کپی از این ایده پیروی می‌کنند که رأس‌های جدیدی که به شبکه اضافه می‌شوند، اتصالات خود را از یک رأس دیگر شبکه تقلید کنند و به همان همسایه‌های رأس انتخاب‌شده متصل شوند.   در ساده‌ترین حالت، رأس‌ها حذف نمی‌شوند. در هر مرحله یک رأس جدید با یک یال منفرد از آن ایجاد می‌کنیم. فرض کنید u گره‌ای باشد که به طور تصادفی از میان گره‌های موجود شبکه تا این مرحله زمانی، انتخاب شده است، فرض می‌کنیم:

(I) با احتمال <math>p</math> ، تنها پارامتر مدل، یال جدید به u اشاره می‌کند.

(II) با احتمال <math>1-p</math> ، یال جدید به مقصد یال خروجی از u (تنها) اشاره می‌کند. (گره جدید با کپی کردن یال خود را می‌سازد.)

فرض (II) احتمال دریافت یال‌های ورودی جدید توسط رأس‌های با درجۀ بالاتر را افزایش می‌دهد. در واقع، از آنجایی که u به طور تصادفی انتخاب می‌شود، احتمال اینکه یک [[صفحه وب]] با درجۀ k یک لینک جدید دریافت کند با <math>(1-p)k</math> ، متناسب است؛ این امر نشان می‌دهد که مکانیسم کپی به طور موثر به یک [[اتصال ترجیحی]] خطی تبدیل می‌شود. 

کومار و همکارانش ثابت کردند که [[توزیع درجه]] انتظاری برای درجۀ ورودی با فرض‌های گفته‌شده <math>P(k_{in})=k^{-(2-p)/(1-p)}</math> است، بدین ترتیب <math>P(k)</math> از [[توزیع توانی|قانون توان]] پیروی می کند که توان آن بین 2 (برای <math>p\rightarrow 0</math> ) و <math>\infty</math> (برای <math>p\rightarrow 1</math> ) تغییر می‌کند، بنابراین این روش ساخت شبکه، [[شبکه بی‌مقیاس]] می‌سازد.

در مدل بالا، کپی رشد خطی دارد؛ مدل‌های دیگری وجود دارند که [[رشد نمایی]] را با فرآیند کپی کردن نتیجه دهند. هم‌چنین مدل‌های دیگری با ساز و کار مشابه وجود دارند که هر کدام سعی در برطرف کردن مشکلات مدل‌های قبلی یا توضیح خواصی از شبکه‌ها را دارند.

مدل‌های بالا کامل نیستند و آن‌ها را می‌توان به روش‌های مختلفی گسترش داد. مدل می‌تواند پیچیده‌تر شود تا انحرافات مشاهده شده از [[توزیع احتمال|توزیع]] [[توزیع توانی|توانی]] را در نظر گرفته و توضیح دهد. به طور مشابه، مدل‌ها را می‌توان گسترش و تغییر داد تا فرآیندهای مرگ یا حذف رأس و یال‌ها را نیز شامل شود و بدین‌وسیله تکامل شبکه را توضیح دهند.

== کاربرد در مدل‌های بدون جهت ==

=== شبکه‌های تعامل پروتئین ===
وازکز بر اساس مدل برهم‌کنش‌های پروتئین تکراری، یک نمودار رشد با ساز و کار کپی کردن پیشنهاد کرد. در هر مرحله زمانی یک نمونه اولیه به طور تصادفی انتخاب می شود. با احتمال q همسایه‌های نمونۀ اولیه کپی می‌شوند و با احتمال p یک یال برای نمونه اولیه ایجاد می‌شود. <ref name="Vazquez">A. Vazquez, A. Flammini, A. Maritan, A. Vespignani, Modeling of protein interaction networks, {{Arxiv|cond-mat/0108043}}.</ref>

=== شبکه‌های پروتئوم ===
سول یک نمودار رشد پیشنهاد کرد که با یک بستر 5 حلقه‌ای اولیه آغاز می‌شود؛ در هر مرحلۀ زمانی یک گره جدید اضافه شده و یک نمونۀ اولیه به طور تصادفی انتخاب می‌شود. همسایه‌های نمونه اولیه با احتمال δ کپی می‌شوند. علاوه بر این، گره‌هایی تصادفی با احتمال α=β/N به گره تازه اضافه شده متصل می‌شوند، که در آن δ و β پارامترهایی بین (0،1) و N تعداد کل رأس‌ها در مرحله زمانی مورد نظر است. <ref name="Sole">R. V. Sole, R. Pastor-Satorras, E. Smith, T. B. Kepler, A model of large-scale proteome evolution, {{Arxiv|cond-mat/0207311}}.</ref>

== مدل‌های جهت‌دار ==

=== شبکه‌ جهانی وب و شبکه‌ ارجاعات ===
وازکز مدل رشدی را بر اساس مکانیزم «کپی» بازگشتی پیشنهاد کرد که در آن رأس جدید به دومین همسایه نزدیک، سومین همسایه نزدیک و غیره یک رأس متصل می‌شود (نویسندگان آن را مکانیسم «راه رفتن تصادفی» می‌نامند). <ref name="VazquezII">A. Vazquez, Knowing a network by walking on it: emergence of scaling, {{Arxiv|cond-mat/0006132}}.</ref>

=== رشد شبکه با فرآیند کپی (GNC) ===
کراپیوسکی<ref>{{یادکرد وب|نشانی=https://www.santafe.edu/people/profile/paul-krapivsky|عنوان=P. L. Krapivsky}}</ref> و [[سیدنی ردنر|ردنر]] مدلی برای رشد شبکه پیشنهاد کردند که در آن گره تازه معرفی‌شده به طور تصادفی یک گره را به عنوان هدف انتخاب می‌کند و به آن و هم‌چنین به تمام رأس‌های همسایه آن (آن‌هایی که گره هدف به آن‌ها اشاره می‌کند) پیوند برقرار می‌کند. اگر گره هدف جزو گره‌های پایۀ اولیه باشد، هیچ پیوند اضافی توسط مکانیسم کپی ایجاد نمی‌شود. اگر گره تازه معرفی شده همیشه یک گره پایه را به عنوان هدف انتخاب کند، یک نمودار ستاره‌ای ایجاد می‌شود. هم‌چنین، اگر رأس هدف همیشه جدیدترین رأس شبکه باشد، تمام رأس‌های قبلی همسایۀ هدف هستند و فرآیند کپی کردن، یک [[گراف کامل]] را خواهد ساخت. بنابراین، تعداد کل پیوندها <math>L_N</math> در شبکه‌ای با N رأس می‌تواند از N-1 (گراف ستاره‌ای) تا N(N-1)/2 (گراف کامل) باشد. هم‌چنین توجه داشته باشید که تعداد پیوندهای خروجی از هر رأس جدید (درجه خروجی) می تواند بین 1 و تعداد رأس‌های فعلی آن مرحله باشد. <ref name="Krapivsky">{{Cite journal|last=Krapivsky|first=P. L.|last2=Redner|first2=S.|date=2005-03-17|title=Network growth by copying|journal=Physical Review E|publisher=American Physical Society (APS)|volume=71|issue=3|page=036118|arxiv=cond-mat/0410379|doi=10.1103/physreve.71.036118|issn=1539-3755}}</ref>

== یادداشت‌ها ==
<references group="" responsive="1"></references>

== منابع ==

* Kleinberg, JM, R. Kumar, P. Raghavan, S. Rajagopalan, and A. Tomkins, 1999, مجموعه مقالات کنفرانس بین المللی ترکیبیات و محاسبات.
* Kumar, R., P. Raghavan, S. Rajagopalan, D. Sivakumar, AS Tomkins and E. Upfal, 2000a, مجموعه مقالات نوزدهمین سمپوزیوم اصول سیستم های پایگاه داده.
* Kumar, R., P. Raghavan, S. Rajagopalan, D. Sivakumar, AS Tomkins and E. Upfal, 2000b, مجموعه مقالات چهل و یکمین سمپوزیوم IEEE در مبانی علوم کامپیوتر.
* P. L. Krapivsky and S. Redner, Phys. Rev. E 71, 036118 – Published 17 March 2005
<nowiki>
[[رده:نظریه گراف]]</nowiki>
[[رده:نظریه گراف]]