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

روش کپی کردن (به انگلیسی: Copying Mechanism) فرآیندی است که در نتیجۀ آن، یک شبکه‌‌ بی‌مقیاس با استفاده از فرآیندی مکرر که در آن گره‌ها با جهش از گره‌های موجود کپی می‌شوند، ساخته شده و رشد می‌کند. در مدل عمومی آن، یک شبکۀ اولیۀ در حال رشد داده می‌شود و در هر مرحلۀ زمانی، یک گره جدید با درجۀ مشخص k (تعداد یال خروجی رأس جدید) به شبکه اضافه می‌شود. در قدم بعدی یک گره از شبکه به طور تصادفی انتخاب شده و گره جدید، اتصالات گره انتخاب‌شده را تقلید می‌کند و در نتیجۀ آن همسایه‌های مشترکی با گره انتخاب‌شده خواهد داشت. ^[۱]

ریشه‌ها

جان کلینبرگ و هم‌کارانش این مدل را برای توضیح شبکۀ ارجاعات مقالات و شبکه جهانی وب پیشنهاد کردند.^[۲] از جمله دلایل ارائۀ این مدل برای این شبکه‌ها موارد زیر هستند:

برخی از نویسندگان صفحات وب، به یک موضوع جالب اما جدید بین صفحات خاصی توجه می‌کنند و به صفحاتی که این اشتراک را دارند پیوند می‌دهند. صفحات ایجاد شده با این انگیزه، با انتخاب تصادفی از بین صفحات موجود مدل‌سازی می‌شوند.
بیشتر نویسندگان به موضوعات خاصی که قبلاً ارائه شده‌اند علاقه‌مند هستند و پیوندهایی به صفحات مربوط به این موضوعات را جمع‌آوری می‌کنند. صفحات ایجاد شده به این روش را می‌توان با کپی کردن گره‌ها مدل‌سازی کرد.
نویسندگان یک مقاله ممکن است به سادگی کل (یا بخشی از) ارجاعات یک مقالۀ مرتبط (با مقالۀ خود) را در ارجاعات مقالۀ خود کپی کنند، زیرا نویسندگان ممکن است با تعداد کمی مقالۀ مرتبط آشنا باشند و بقیۀ مقالات ارجاعی را به سادگی از مقالات مشابه تقلید کنند.^[۱]^[۳]

توضیح مدل

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

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

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

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

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

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

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

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

شبکه‌های تعامل پروتئین

وازکز بر اساس مدل برهم‌کنش‌های پروتئین تکراری، یک نمودار رشد با ساز و کار کپی کردن پیشنهاد کرد. در هر مرحله زمانی یک نمونه اولیه به طور تصادفی انتخاب می شود. با احتمال q همسایه‌های نمونۀ اولیه کپی می‌شوند و با احتمال p یک یال برای نمونه اولیه ایجاد می‌شود. ^[۴]

شبکه‌های پروتئوم

سول یک نمودار رشد پیشنهاد کرد که با یک بستر 5 حلقه‌ای اولیه آغاز می‌شود؛ در هر مرحلۀ زمانی یک گره جدید اضافه شده و یک نمونۀ اولیه به طور تصادفی انتخاب می‌شود. همسایه‌های نمونه اولیه با احتمال δ کپی می‌شوند. علاوه بر این، گره‌هایی تصادفی با احتمال α=β/N به گره تازه اضافه شده متصل می‌شوند، که در آن δ و β پارامترهایی بین (0،1) و N تعداد کل رأس‌ها در مرحله زمانی مورد نظر است. ^[۵]

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

شبکه‌ جهانی وب و شبکه‌ ارجاعات

وازکز مدل رشدی را بر اساس مکانیزم «کپی» بازگشتی پیشنهاد کرد که در آن رأس جدید به دومین همسایه نزدیک، سومین همسایه نزدیک و غیره یک رأس متصل می‌شود (نویسندگان آن را مکانیسم «راه رفتن تصادفی» می‌نامند). ^[۶]

رشد شبکه با فرآیند کپی (GNC)

کراپیوسکی^[۷] و ردنر مدلی برای رشد شبکه پیشنهاد کردند که در آن گره تازه معرفی‌شده به طور تصادفی یک گره را به عنوان هدف انتخاب می‌کند و به آن و هم‌چنین به تمام رأس‌های همسایه آن (آن‌هایی که گره هدف به آن‌ها اشاره می‌کند) پیوند برقرار می‌کند. اگر گره هدف جزو گره‌های پایۀ اولیه باشد، هیچ پیوند اضافی توسط مکانیسم کپی ایجاد نمی‌شود. اگر گره تازه معرفی شده همیشه یک گره پایه را به عنوان هدف انتخاب کند، یک نمودار ستاره‌ای ایجاد می‌شود. هم‌چنین، اگر رأس هدف همیشه جدیدترین رأس شبکه باشد، تمام رأس‌های قبلی همسایۀ هدف هستند و فرآیند کپی کردن، یک گراف کامل را خواهد ساخت. بنابراین، تعداد کل پیوندها $L_{N}$ در شبکه‌ای با N رأس می‌تواند از N-1 (گراف ستاره‌ای) تا N(N-1)/2 (گراف کامل) باشد. هم‌چنین توجه داشته باشید که تعداد پیوندهای خروجی از هر رأس جدید (درجه خروجی) می تواند بین 1 و تعداد رأس‌های فعلی آن مرحله باشد. ^[۸]

یادداشت‌ها

↑ ^۱٫۰ ^۱٫۱ Newman، Mark (۲۰۱۰). Node Copying Models (ویراست دوم). ص. ۴۷۲.
↑ Kleinberg، Jon M.؛ Kumar، Ravi؛ Raghavan، Prabhakar؛ Rajagopalan، Sridhar؛ Tomkins، Andrew S. (۱۹۹۹). «The Web as a Graph: Measurements, Models, and Methods».
↑ Krapivsky، P. L.؛ Redner، S. (۲۰۰۵). «Network Growth by Copying». Phys. Rev. ۷۱.
↑ A. Vazquez, A. Flammini, A. Maritan, A. Vespignani, Modeling of protein interaction networks, آرخیو:cond-mat/0108043.
↑ R. V. Sole, R. Pastor-Satorras, E. Smith, T. B. Kepler, A model of large-scale proteome evolution, آرخیو:cond-mat/0207311.
↑ A. Vazquez, Knowing a network by walking on it: emergence of scaling, آرخیو:cond-mat/0006132.
↑ «P. L. Krapivsky».
↑ Krapivsky, P. L.; Redner, S. (2005-03-17). "Network growth by copying". Physical Review E. American Physical Society (APS). 71 (3): 036118. arXiv:cond-mat/0410379. doi:10.1103/physreve.71.036118. ISSN 1539-3755.

منابع

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

[[رده:نظریه گراف]]

[kogias-1] ۱٫۰ ^۱٫۱ Newman، Mark (۲۰۱۰). Node Copying Models (ویراست دوم). ص. ۴۷۲.

[2] Kleinberg، Jon M.؛ Kumar، Ravi؛ Raghavan، Prabhakar؛ Rajagopalan، Sridhar؛ Tomkins، Andrew S. (۱۹۹۹). «The Web as a Graph: Measurements, Models, and Methods».

[3] Krapivsky، P. L.؛ Redner، S. (۲۰۰۵). «Network Growth by Copying». Phys. Rev. ۷۱.

[Vazquez-4] A. Vazquez, A. Flammini, A. Maritan, A. Vespignani, Modeling of protein interaction networks, آرخیو:cond-mat/0108043.

[Sole-5] R. V. Sole, R. Pastor-Satorras, E. Smith, T. B. Kepler, A model of large-scale proteome evolution, آرخیو:cond-mat/0207311.

[VazquezII-6] A. Vazquez, Knowing a network by walking on it: emergence of scaling, آرخیو:cond-mat/0006132.

[7] «P. L. Krapivsky».

[Krapivsky-8] Krapivsky, P. L.; Redner, S. (2005-03-17). "Network growth by copying". Physical Review E. American Physical Society (APS). 71 (3): 036118. arXiv:cond-mat/0410379. doi:10.1103/physreve.71.036118. ISSN 1539-3755.

[۱]

[۲]

[۳]

[۴]

[۵]

[۶]

[۷]

[۸]