معیارهای شباهت مبتنی بر گراف

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

• ضریب خوشه بندی محلی[1]

در سال های اخیر معیار ضریب خوشه بندی محلی چه در حوزه تئوری و چه در حوزه عملی در میان محققان بسیار مورد توجه بوده است. در حوزه شناسایی اجتماعات، با کمک این معیار می توان تعیین کرد که گره ها تا چه میزان تمایل به شرکت در یک اجتماع را دارند. به عبارت دیگر معیار ضریب خوشه بندی نشان می دهد که همسایگی یک گره تا چه میزان همبند بوده و به یک اجتماع شبیه است. این معیار توسط Ding و دیگران جهت شناسایی نفوذگران در شبکه استفاده شده و در این پژوهش تنها به عنوان مقایسه استفاده می شود. برای محاسبه این معیار از فرمول زیر استفاده می شود:

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

• ضریب خوشه بندی وزن دار محلی[2]

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

در فرمول بالا متغییر  نشان دهنده وزن تخمین زده شده برای سه گره – i و j و k – مرتبط با هم می باشد. در قسمت صورت مجموع تخمین وزن همسایه های از گره مورد نظر که خود با هم در ارتباطند آورده می شود. در قسمت مخرج نیز مجموع تخمین وزن هر دو همسایه گره مورد نظر، فارغ از ارتباطشان با یکدیگر آورده می شود. این تخمین وزن بر اساس چهار معیار انجام می شود:

• حداقل وزن لبه
• حداکثر وزن لبه
• میانگین عددی وزن لبه
• میانگین حسابی وزن لبه

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

در شکل زیر در قسمت سمت چپ، یک گراف دوسویه را مشاهده می کنید که با انجام فرآیند تبدیل به یک گراف یک سویه وزن دار تبدیل شده است. در محاسبه ضریب خوشه بندی و ضریب خوشه بندی وزن دار، تمامی گره ها به جز گره شماره 8 مقادیر یکسان دریافت می کنند. اما گره شماره 8 دارای ضریب خوشه بندی 0.33 و ضریب خوشه بندی وزن دار 0.5 می باشد. در نتیجه معیار ضریب خوشه بندی گره های 7 و 8 را به عنوان نفوذی شناسایی می کند. حال آنکه ضریب خوشه بندی وزن دار تنها گره 7 را به عنوان نفوذی شناسایی می کند. در نتیجه معیار خوشه بندی وزن دار دارای نرخ خطای کمتری می باشد.

• تبدیل گراف دوسویه به یک سویه

[1] Local Clustering Coefficient

[2] Weighted Local Clustering Coefficient