با هم همپوشانی جامعه از شبکه های دو طرفه بر اساس تراکم جدید جامعه

تشخیص جامعه نقش اساسی در درک توپولوژی شبکه و استخراج اطلاعات اساسی دارد. یک شبکه دو طرفه یک شبکه پیچیده با اصالت و کاربرد مهمتر از یک شبکه یک حالته در دنیای واقعی است. بسیاری از جوامع در شبکه وجود دارند که ساختارهای همپوشانی طبیعی را در دنیای واقعی ارائه می دهند. با این حال ، بیشتر تحقیقات بر تشخیص ساختارهای جامعه غیر همپوشانی در شبکه دو حزب متمرکز است و وضوح عملکرد ارزیابی موجود برای شایستگی ساختار جامعه محدود است. بنابراین ، ما یک عملکرد جدید برای تشخیص جامعه و ارزیابی شبکه دو طرفه ، به نام چگالی جامعه d پیشنهاد می کنیم. و بر اساس چگالی جامعه ، یک الگوریتم تشخیص جامعه شبکه دو طرفه DSNE (استخراج دامنه زیر جامعه چگالی چگالی) ارائه شده است ، که برای همپوشانی تشخیص جامعه از یک دیدگاه میکرو مؤثر است. آزمایشات مبتنی بر شبکه های مصنوعی تولید شده و شبکه های دنیای واقعی نشان می دهد که الگوریتم DSNE نسبت به برخی از الگوریتم های عالی موجود برتر است. در مقایسه ، چگالی جامعه (D) بهتر از مدولار شبکه دو طرفه است.

1. مقدمه

یک شبکه پیچیده شبکه با درجه بالایی از پیچیدگی است و پیچیدگی آن عمدتاً در مقیاس بزرگ سیستم ، ساختارهای متنوع و انواع پیچیده گره ها منعکس می شود. با توجه به تعداد انواع گره ، شبکه پیچیده را می توان به عنوان شبکه یک حالته و شبکه چند حالته طبقه بندی کرد. شبکه ای که فقط یک نوع گره را شامل می شود ، شبکه یک حالته مانند شبکه های مالی [1] ، شبکه های اجتماعی [2] و اینترنت [3] نامیده می شود. شبکه حاوی بیش از دو نوع گره در شبکه ، شبکه چند حالته نامیده می شود. شبکه دو حزب یکی از شبکه های چند حالته است که به عنوان دو نوع گره تعریف شده است. هیچ اتصال داخلی از همان نوع گره وجود ندارد ، اما لبه هایی وجود دارد که فقط بین انواع مختلف گره ها وجود دارد. در دنیای واقعی ، انواع مختلفی از شبکه های دو طرفه مانند شبکه های پروتئین [4] و شبکه های همکاری علمی وجود دارد [5]. جامعه یک شبکه پیچیده مجموعه ای است که از رئوس در شبکه پیچیده تشکیل شده است. رئوس در همان جامعه از نزدیک با هم وصل شده است ، در حالی که راس های جوامع مختلف به سختی به هم وصل می شوند. مانند انجمن های مختلف به طور کلی تمایل به برقراری ارتباط با افراد در همان انجمن و نه با افراد خارج از انجمن. شکل 1 نمونه ای از جامعه از شبکه دو طرفه شرکت های آفریقای جنوبی را نشان می دهد [6]. مناطقی که توسط خطوط آبی و زرد رنگ به ترتیب نشان دهنده جامعه 1 و جامعه 2 هستند ، و گره های سبز نشان دهنده گره های همپوشانی در جامعه است. به دلیل کاربرد گسترده و جهانی بودن آن ، شبکه دو طرفه کانون محققان فعلی است. دیدگاه ها و روش های مختلفی در مورد تحقیقات پیچیده شبکه وجود دارد. به عنوان یک ویژگی مهم ، می توانیم توپولوژی عمیق تر ، معنای پنهان و اطلاعات شبکه را از طریق تشخیص ساختار جامعه بدست آوریم. در دنیای واقعی ، یک جامعه شبکه دو طرفه برای حل بسیاری از مشکلات عملی یافت شده است. به عنوان مثال ، مطالعه معدن شبکه دو طرفه مبنای تحقیق و روش جدیدی را برای مدل اپیدمی فراهم می کند [7]. در زمینه توصیه ، تحقیقات در مورد تشخیص ساختار جامعه از شبکه دو طرفه می تواند روش جدیدی را برای فناوری توصیه سیستم های شبکه دو طرفه ارائه دهد. به عنوان مثال ، در سیستم توصیه شبکه دو طرفه کاربران و کالاهای تجارت الکترونیکی ، اگر کاربران با توجه به ویژگی های خود تقسیم شوند ،

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

با توجه به رابطه فرعی گره ها ، ساختار جامعه را می توان به ساختار همپوشانی جامعه و ساختار جامعه غیر همپوشانی تقسیم کرد. الگوریتم های تشخیص جامعه سنتی بیشتر بر جوامع غیر همپوشانی در شبکه دو حزب متمرکز است ، در حالی که تعداد کمی از مطالعات بر جوامع همپوشانی در شبکه دو طرفه متمرکز است. اما در دنیای واقعی ، یک گره معمولاً بیش از یک ویژگی دارد. یک گره می تواند متعلق به بیش از یک جامعه باشد. به عنوان مثال ، در شبکه همکاری علمی [5] ، نویسندگان مختلف می توانند یک مقاله بنویسند و یک نویسنده می تواند مقالات مختلفی را امضا کند. بنابراین ، ارزش عملی و ارزش تحقیقاتی علمی بسیار مهم تری برای بررسی تشخیص جوامع همپوشانی شبکه دو طرفه دارد.

به تازگی ، با توجه به اینکه محققان بیشتر و بیشتر به حوزه تشخیص جامعه شبکه دو طرفه می روند ، تعداد کمی از الگوریتم ها در زمینه تشخیص جامعه پدید آمده اند [7،8،9،10،11]. به طور کلی ، این الگوریتم ها می توانند به دو دسته تقسیم شوند. یکی این است که شبکه دو حزب را به شبکه یک حالته [12،13،14] ارائه دهید. مزایای این رویکرد می تواند بر اساس نتایج تحقیق فعلی شبکه یک حالته باشد که کار ساده تر است. با این حال ، در ارائه به شبکه یک حالته ، شبکه دو طرفه اطلاعات اصلی را از دست می دهد و نویز را افزایش می دهد. مورد دیگر این است که مستقیماً جامعه را در شبکه دو حزب تشخیص دهید [15]. در مقایسه با پیش بینی شبکه دو طرفه ، کار با آن چالش برانگیزتر است. با این وجود ، اطلاعات اصلی ساختار شبکه را می توان تا حدودی محافظت کرد که در فرآیند طرح ریزی نابود نشود. با این حال ، این نوع رویکرد عمدتاً از ساختار توپولوژی شبکه شروع می شود و تشخیص جامعه را از منظر کلان انجام می دهد. توجه کمی به رابطه بین گره ها و در کشف برخی از ویژگی های ساختاری میکروسکوپی شبکه دو طرفه نیست.

نحوه اندازه گیری شایستگی نتایج الگوریتم تشخیص جامعه یکی دیگر از مشکلات اساسی است. تا کنون، یک شاخص ارزیابی جهانی به رسمیت شناخته شده برای تشخیص جوامع شبکه دو بخشی وجود نداشته است. شاخص های ارزیابی موجود بیشتر بر اساس مدولار بودن شبکه دوبخشی [11،16،17] است و بهبودهایی در آن ایجاد می کند. با این حال، به دلیل محدودیت تفکیک ماژولاریتی [18]، مدولار بودن نمی تواند در مورد محاسن و معایب نتایج تشخیص جامعه در برخی موارد خاص قضاوت کند.

یک شاخص ارزیابی جدید (تراکم جامعه D) پیشنهاد شده است که مشکل محدودیت وضوح مدولار را کاهش می‌دهد و محاسن و معایب شبکه دوبخشی را از نقطه‌ای جدید ارزیابی می‌کند.

یک الگوریتم جدید تشخیص جامعه (Extraction جفت گره زیر جامعه چگالی (DSNE)) پیشنهاد شده است. دارای مزایای یک مدل میکرو شبکه است، یک استراتژی ادغام جدید برای ادغام جامعه اتخاذ می کند، و می تواند ساختار جامعه همپوشانی شبکه دوجانبه را تشخیص دهد.

نتایج تجربی نشان می‌دهد که الگوریتم پیشنهادی از دقت و کارایی الگوریتم‌های دیگر برتری دارد.

2. کارهای مرتبط

در مقایسه با شبکه یک حالته، توپولوژی شبکه دوبخشی پیچیده تر است و جهانی بودن و عملی بودن قوی تری دارد. بنابراین، تحقیق در مورد تشخیص مشکل جامعه شبکه دو جانبه ارزشمندتر است. دو مشکل اصلی در تشخیص جامعه شبکه دو جانبه وجود دارد: یافتن ساختار جامعه به طور مؤثرتر، و دیگری چگونگی ارزیابی محاسن و معایب نتایج تشخیص جامعه. در نتیجه، عمدتاً دو نوع تحقیق در مورد الگوریتم تشخیص جامعه شبکه دوبخشی وجود دارد و شاخص ارزیابی شبکه دوبخشی عمدتاً با هدف بهبود مدولار بودن شبکه دوبخشی است.

2. 1. بر اساس طرح الگوریتم تشخیص جامعه شبکه دو طرفه

روش های پیش بینی شبکه های دو طرفه به شبکه های یک حالته عمدتاً به یک حالت پیش بینی یک حالته و پیش بینی یک حالته تقسیم می شوند. طرح ریزی یک حالته بدون وزنی به سادگی در حال نمایش شبکه های دو طرفه به شبکه های یک حالته است. نیومن و همکاران.[19] با استفاده از یک طرح ریزی راست یک حالته ، یک شبکه دو حزب (شبکه همکاری علمی) را به دو شبکه یک حالته تبدیل کرد. هوروات و همکاران.[20] یک روش آماری را پیشنهاد کرد که الگوریتم طرح ریزی شبکه دو طرفه حاوی یک رابطه واحد را گسترش داده و انواع مختلفی از طرح ریزی روابط را در مجموعه داده های بزرگ حل می کند. Valejo و همکاران.[21] روش لایه بندی سنتی را در فرآیند طرح ریزی شبکه دو طرفه به کار برد ، یک روش چند لایه را بر اساس طرح ریزی پیشنهاد می کند. کامار و همکاران.[22] چارچوبی را پیشنهاد کرد که می تواند به طور همزمان ساختارهای شبکه جوامع مختلف و ارتباط آنها را با مزایایی مانند سازگاری قوی و همگرایی سریع تشخیص دهد. با این حال ، در فرآیند طرح ریزی یک حالته بدون وزنی ، اطلاعات ساختار شبکه ، مانند فرکانس لبه ، ممکن است از بین برود و منجر به کاهش قابل توجهی در صحت تشخیص جامعه با این روش شود. محققان با توجه به نقص آشکار پروژه های مدولار بدون وزنی ، توجه خود را به پروژه های مدولار وزنه برداری تبدیل کردند.

پیش بینی وزن یک حالته ، فرکانس لبه ها را در یک شبکه دو طرفه به وزن لبه ها در یک شبکه یک حالته در طی فرآیند طرح ریزی تبدیل می کند. لیو و همکاران.[23] یک روش جدید ماتریس غیر منفی (F-NMTF) برای خوشه بندی دو نوع گره در یک شبکه دو حزب ارائه داد. ژانگ و همکاران.[12] از ساختاری استفاده کرد که می تواند رابطه بین دو نوع گره ، فاکتورسازی ماتریس دو طرفه متقارن وزنی (WSBMF) را برای تشخیص جوامع همپوشانی در شبکه دو طرفه توصیف کند. وانگ و همکاران.[13] روش جدیدی برای یافتن و گسترش قسمت دوم جامعه اصلی شبکه ارائه داد. به ترتیب دو پارامتر را برای نشان دادن رابطه بین گره ها از یک نوع و گره های ناهمگن تعریف کنید. در ژو و همکاران.[14] ، بر اساس الگوریتم لووین ، الگوریتم دو لووین مناسب برای شبکه دو حزب ارائه شده است ، و یک الگوریتم دو مرحله ای با مدولار سازی جزئی و تعیین قدرت پارتیشن برای تشخیص جامعه شبکه دو طرفه اعمال می شود. Pesantez-Cabrera و همکاران.[24] یک الگوریتم کارآمد به نام Bilouvann را پیشنهاد کرد ، که مجموعه ای از اکتشافات را برای تشخیص سریع و دقیق جامعه در شبکه های دو طرفه پیاده سازی می کند. در مقایسه با پروژه مدولار غیر وزنی ، روش پروژه ماژولار وزنی می تواند از دست دادن اطلاعات ساختاری تا حد زیادی کاهش یابد. با این وجود ، ضرر آن این است که صحت نتایج تشخیص جامعه به محاسبه وزنه ها بستگی دارد ، که عدم اطمینان قابل توجهی دارد و بر استفاده از چنین روش هایی تأثیر می گذارد.

2. 2به طور مستقیم در شبکه دو طرفه پردازش می شود

2. 3معیارهای ارزیابی تشخیص جامعه

اگر شاخص ارزیابی علمی نتایج تشخیص جامعه وجود نداشته باشد، الگوریتم تشخیص جامعه از بین می رود، بنابراین نحوه ارزیابی شایستگی نتایج تشخیص جامعه یکی دیگر از موضوعات مهم در تحقیقات تشخیص جامعه است. به ویژه برای جوامع همپوشانی، معیارهای ارزیابی ساختار جامعه بسیار پیچیده است. ارائه یک شاخص ارزیابی واحد و شناخته شده دشوار است. باربر [16] مدولار بودن شبکه سنتی یک حالته را به شبکه دو بخشی گسترش داد. موراتا و همکاران[17] نوع دیگری از مدولار بودن شبکه‌های دوبخشی را پیشنهاد کرد، که می‌توان آن را با یک جفت دو گروه عددی در دو جهت نشان داد، که امکان مطابقت یک به چند جوامع از انواع مختلف راس را فراهم می‌کند. سوزوکی و همکاران[34] یک روش اندازه‌گیری مدولاریته جدید بر اساس M. E. J Newman پیشنهاد کرد که برای شبکه‌های دوبخشی و شبکه‌های غیر یکنواخت کاربرد دارد. چانگ و همکاران[30] یک روش ارزیابی مدولاریته جدید را پیشنهاد کرد که بر اساس روش M. E. J Newman، مدولار بودن را به تشخیص جامعه همپوشانی گسترش داد. این معیار ارزیابی می تواند یافته های جوامع همپوشانی را در شبکه های دوبخشی ارزیابی کند. تمام معیارهای ارزیابی که در بالا توضیح داده شد با وضوح مدولاریته [18] محدود می شوند. مسئله محدودیت وضوح برای اولین بار توسط Fortunato و همکاران ارائه شد.[35] در سال 2007. فورتوناتو و همکاران.[36] دریافتند که ماژولاریت با وضوح چندگانه ممکن است قادر به شناسایی تعداد زیادی از ساختارهای جامعه شبکه با ویژگی های بدون مقیاس در واقعیت نباشد. به طور خاص، ماژولار بودن چند وضوح ممکن است برخی از جوامع کوچک را به جوامع بزرگ ادغام کند و ممکن است جوامع بزرگ را به جوامع کوچک تقسیم کند. لی و همکاران[37] یک تابع انبوه از تراکم پارتیشن جامعه برای اندازه گیری کیفیت ساختار جامعه در یک شبکه دوبخشی پیشنهاد کرد. با این حال، این تابع توده فقط برای ساختار اجتماع همپوشانی پرواز در شبکه دوبخشی قابل استفاده است.

3. تراکم جامعه

این بخش به دو بخش تقسیم می شود: تعریف چگالی جامعه D ، استدلال D محدودیت وضوح مدولار را تا حدی حل می کند. ما می خواهیم چگالی جامعه را تعریف کنیم تا اندازه گیری کیفیت تقسیم جامعه عمدتاً به دلیل مشکلات باقی مانده از تاریخ مدولار باشد. آخرین روش ها را به عنوان مثال بگیرید. چانگ و همکاران.[30] مدولار پیشنهادی E Q B مناسب برای ساختار همپوشانی شبکه دو طرفه ، اما هنوز هم با وضوح مدولار محدود است. لی [37] چگالی پارتیشن دو طرفه را پیشنهاد کرد ، که می تواند به طور مؤثر محدودیت وضوح مدولار را کاهش دهد و جامعه را به عنوان یک کل در نظر بگیرد و نمی تواند برای همپوشانی جوامع مورد استفاده قرار گیرد. اگرچه این روشها می توانند ساختار جامعه را تشخیص دهند ، اما آنها از دیدگاه خرد ، مانند رابطه بین جفت گره در جامعه ، ساختار جامعه را در نظر نمی گیرند. بر این اساس ، از نظر میکرو ، این مقاله رابطه بین جفت های گره در جامعه را در نظر می گیرد و یک استاندارد ارزیابی مناسب برای ساختار همپوشانی شبکه دو طرفه را ارائه می دهد ، که می تواند به طور مؤثر محدودیت وضوح مدولار را کاهش دهد.

3. 1تعاریف کلیدی< u ∣ u ∈ U >با توجه به یک شبکه دو طرفه g = (u ، v ، e) (u ≠ ⌀ ، v ≠ ⌀ ، u ∩ v = 0) بدون وزن ، بدون جهت و لبه ها فقط بین گره ها از انواع مختلف وجود دارد. U =< v ∣ v ∈ V >: تو یک گره یک گره است ، v =

: V یک نوع گره دیگر است. A تعداد گره های نوع U را نشان می دهد ، و B تعداد گره های نوع V را نشان می دهد. E مجموعه ای از لبه های متصل شده توسط دو نوع گره را نشان می دهد ، و (u ، v) یک جفت گره را که توسط Edge E (U ، V) متصل شده اند نشان می دهد. یک نمودار مثال از یک شبکه دو حزب در شکل 2 نشان داده شده است. پنج گره U و شش گره V وجود دارد که در کل سیزده لبه وجود دارد.< ( U 1 , V 1 ) , ( U 1 , V 2 ) , ( U 1 , V 3 ) ) >در یک شبکه دو طرفه G = (U ، V ، E) ، P N (U) مجموعه ای از همه جفت های گره حاوی گره U ، L (P n (u)) را نشان می دهد که تعداد جفت های گره u را در U و سپس L (نشان می دهد (p n (u)) = l (u) تعداد کل جفت های گره در مجموعه است. به همین ترتیب ، p n (v) مجموعه ای از همه جفت های گره حاوی گره V را نشان می دهد ، ما اجازه می دهیم l (p n (v)) تعداد جفت های گره v در v و سپس l (p n (v)) = l (v) باشدتعداد کل جفت های گره در مجموعه است. همانطور که در شکل 3 نشان داده شده است: برای گره u 1 ، p n (u 1) =< ( U 1 , V 1 ) , ( U 2 , V 1 ) , ( U 4 , V 1 ) , ( U 6 , V 1 ) >؛برای گره V 1 ، p n (v 1) =