استخراج ویژگی‌های سطح گره از شبکه‌های گراف برای مدل‌های یادگیری ماشین

۱. مقدمه

این ادامه مجموعه وبلاگ‌های من در شبکه‌های گراف و دومین وبلاگ از این مجموعه است. مقاله اول برخی از مفاهیم مقدماتی برجسته شامل آناتومی یک گراف مانند: گره‌ها، لبه‌ها و تعریف گراف‌های جهت‌دار و غیر جهت‌دار را پوشش داد. این مقاله همچنین به جزئیات نمایش عددی یک گراف/مفهومی از: ماتریس مجاورت، فهرست لبه، فهرست مجاورت پرداخت. شبکه‌های گراف جالبی مانند - گراف‌های دو طرفه و شبکه‌های تا شده نیز در مقاله اول این مجموعه مورد بحث قرار گرفتند. برخی از این موارد در شکل تلفیقی زیر نشان داده شده است:

شکل: مروری بر بحث‌های مقاله اول مجموعه

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

۱) موارد استفاده پیش‌بینی سطح گره.

۲) موارد استفاده پیش‌بینی سطح لبه – که جفت‌های گره را در نظر می‌گیرد و سعی می‌کند پیش‌بینی کند که آیا گره‌ها متصل هستند یا خیر.

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

 

شکل: سطح گره | سطح پیوند | وظایف پیش‌بینی سطح گراف در گراف‌ها

برای یک خط لوله یادگیری ماشین سنتی، تلاش‌ها بر روی مهندسی ویژگی - طراحی ویژگی‌های مناسب، انجام می‌شود. در گراف‌ها می‌توانیم به دو نوع ویژگی فکر کنیم:

در مرحله اول، گره‌ها قبلاً دارای برخی از ویژگی‌های مرتبط با آنها هستند - همانطور که در مقاله قبلی من در بخش 8 توضیح داده شد.

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

بنابراین، ما به دو نوع ویژگی در گراف‌ها فکر می‌کنیم: ویژگی‌هایی که ویژگی‌ها و ویژگی‌های گره‌ها را توصیف می‌کنند و ویژگی‌های ساختاری که توپولوژی را توصیف می‌کنند.

شکل: ویژگی‌های ساختاری که توپولوژی گراف را توصیف می‌کند

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

شکل: تصویری از یادگیری ماشین سنتی در گراف‌ها

این مقاله بر روی طراحی ویژگی‌های ساختاری به منظور تغذیه و آموزش یک مدل یادگیری ماشین تمرکز خواهد کرد. ویژگی‌های ساختاری شامل موارد زیر خواهد بود:

الف) پیش‌بینی سطح گره

ب) پیش‌بینی سطح لبه

ج) پیش‌بینی سطح گراف

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

2. ویژگی‌های سطح گره:

اجازه دهید ابتدا در مورد وظایف سطح گره اجازه دهید ابتدا در مورد وظایف سطح گره و ویژگی‌های ساختاری که گره‌های جداگانه را توصیف می‌کنند صحبت کنیم. اجازه دهید فرض کنیم که همانطور که در شکل زیر نشان داده شده است با یک مسئله دسته‌بندی گره سروکار داریم [با توجه به گره‌های قرمز و سبز رنگ گره‌های خاکستری را می‌خواهیم]

شکل: یک مسئله دسته‌بندی گره

هدف در این مسئله مشخص کردن ساختار و موقعیت گره در شبکه است. 4 مفهوم مختلف وجود دارد که ما را به انجام این کار سوق می‌دهد:

۱. درجه گره

۲. مرکزیت گره

۳. ضریب خوشه‌بندی

۴. گرافلت‌ها

مفاهیم فوق در بخش‌های زیر مورد بحث قرار گرفته است.

شکل: ویژگی‌های سطح گره (در زیر توضیح داده شده است)

3. درجه گره:

درجه گره نشان دهنده تعداد یال‌هایی است که گره دارد - همانطور که در شکل زیر نشان داده شده است. kA، kB، kC و kD نشان دهنده درجه گرهرهای A، B، C و D هستند که به ترتیب 1، 2، 3،4 هستند. با این حال، درجه گره به خودی خود نمی‌تواند وسیله‌ای برای توصیف ویژگی‌های یک گره باشد. به عنوان مثال، در شکل زیر، گره C و E دارای درجه 3 هستند، حتی اگر در مکان‌های مختلف شبکه باشند - بنابراین، این از طریق درجه گره قابل تشخیص نیست.

بنابراین می‌توان گفت که درجه گره فقط همسایه‌های گره را بدون تاکید بر اهمیت گره حساب می‌کند.

شکل: تصویر مفهوم درجه گره

شکل: گره‌های Colour-coding با توجه به درجه آنها، با درجه بالاتر با رنگ تیره‌تر نشان داده شده است

4. مرکزیت گره:

مرکزیت گره تلاش می‌کند تا مشخص کند که گره چقدر در گراف اهمیت دارد (که درجه گره قادر به انجام آن نبود)، بنابراین، راه‌های زیادی وجود دارد که از طریق آنها می‌توانیم مرکزیت گره را مدل کنیم، مانند:

·         مرکزیت ارزش ویژه

·         مرکزیت بینابینی

·         مرکزیت نزدیکی

معیارهای دیگری برای اهمیت یک گره وجود دارد که در این مقاله مورد بحث قرار نگرفته است زیرا موارد فوق برجسته‌ترین معیارها هستند. اجازه دهید درک کنیم که چگونه هر یک از موارد بالا اهمیت یک گره را مشخص می‌کند.

4.1 مرکزیت بردار ویژه:

مرکزیت بردار ویژه اهمیت یک گره را می‌سنجد و در عین حال به اهمیت همسایگان آن توجه می‌کند. برای مثال، یک گره با 300 اتصال نسبتاً بی‌اهمیت در لینکدین، مرکزیت بردار ویژه کمتر از 300 اتصال بسیار محبوب دارد.

از نظر ریاضی، با انجام یک محاسبه ماتریس مشخص می‌شود که با استفاده از ماتریس مجاورت، آنچه را که "بردار ویژه اصلی" نامیده می‌شود، بدست آوریم [من در مورد ماتریس مجاورت در قسمت 1 این سری از وبلاگ‌ها در بخش 7 بحث کرده‌ام].

یعنی:

از نظر ریاضی، یک گره در صورتی مهم تلقی می‌شود که توسط گره‌های همسایه مهمی که در بالا ذکر شد احاطه شده باشد:

معادله ریاضی که اهمیت گره را به عنوان مجموع اهمیت همسایگان آن نشان می‌دهد.

این رابطه ریاضی نشان می‌دهد که اهمیت گره مجموع اهمیت همسایگان آن در شبکه است که با λ نرمال شده است.

در معادله بالا:

§         "λ" عامل نرمال‌سازی است.

§         "c" بردار معیار مرکزیت تمام گره‌های مجاور گره v است.

§         "A" ماتریس مجاورت گراف است.

مسئله یک مسئله ارزش ویژه است که با:

 λc = Ac

اصل اصلی مرکزیت بردار ویژه این است که پیوندهای گره‌های مهم (که با درجه گره معیار می‌شود) ارزش بیشتری نسبت به پیوندهای گره‌های بی‌اهمیت دارند. همه گره‌ها یکسان شروع می‌شوند، اما با پیشرفت محاسبات، "گره‌هایی با لبه‌های بیشتر" اهمیت پیدا می‌کنند. این اهمیت به گره‌هایی که آنها به آنها متصل هستند منتشر می‌شود. پس از بارها محاسبه مجدد، مقادیر تثبیت می‌شوند و در نتیجه مقادیر نهایی مرکزیت بردار ویژه  ایجاد می‌شود.

تفسیر فیزیکی یک مسئله ارزش ویژه:

در مبحث مکانیک، اگر "رویداد" وجود داشته باشد، می‌توانید به عنوان یک بردار نشان دهید. به عنوان مثال نوسان یک پل، و مقداری دگرگونی خطی (مثلاً تندبادهای منظم باد) روی آن اعمال می‌شود، مؤلفه رویداد در جهت بردار ویژه به سادگی در مقدار ویژه مربوط ضرب می‌شود که ممکن است منجر به تقویت یا کاهش اثر رویداد شود. یا به همان شکل باقی بماند (مانند مسئله ارتعاش، که یک مسئله ارزش ویژه است). 

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

4.2 مرکزیت Betweenness:

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

از نظر ریاضی، مرکزیت بین گره معین، جمع بین جفت گره‌های s و t از طریق گره v است که با تعداد کل کوتاه‌ترین مسیرهای بین s و t در سایر گره‌ها نیز نرمال شده است، همانطور که در معادله ریاضی نشان داده شده است. زیر:

معادله: معادله ریاضی برای تعیین مرکزیت بین

به عنوان مثال، در شبکه نشان داده شده در زیر، گره های A، B و E در لبه شبکه قرار دارند، هیچ جفت گره‌ای از طریق گره‌های A، B و E به هم متصل نمی‌شوند. بنابراین، مرکزیت بین A، B و E، ۰ است.

شکل: شبکه مثالی برای محاسبه مرکزیت بین

اکنون با در نظر گرفتن گره “C” در همان شبکه، می‌توان مشاهده کرد که:

§         مسیر A به B از طریق C (A-C-B) عبور می‌کند و هیچ ارتباط دیگری بین A و B به جز A-C-B وجود ندارد.

§         به همین ترتیب، مسیر A به D باید از C (A-C-D) عبور کند و هیچ ارتباط دیگری بین A و D به جز A-C-D وجود ندارد.

§         و مسیر A به E باید از C (A-C-D-E) بگذرد و بین A و E غیر از A-C-D-E ارتباط دیگری وجود ندارد.

بنابراین، مرکزیت بین گره C به صورت زیر است:

و با در نظر گرفتن گره D، در همان شبکه. با استدلال مشابه بالا:

·         کوتاه‌ترین مسیر بین B و E از D می‌گذرد و راه دیگری برای اتصال B و E وجود ندارد

·         کوتاه‌ترین مسیر بین A و E از D (A-C-D-E) می‌گذرد. هیچ مسیر دیگری بین A و E به جز A-C-D-E وجود ندارد

·         کوتاه‌ترین مسیر بین C و E از D می‌گذرد و راه دیگری برای اتصال C و E وجود ندارد

4.3 مرکزیت نزدیکی:

مرکزیت نزدیکی جنبه دیگری از موقعیت گره را به تصویر می‌کشد. این نشان می‌دهد که یک گره چقدر به گره‌های دیگر نزدیک است. به عنوان میانگین طول کوتاه‌ترین مسیر گره به گره‌های دیگر در شبکه محاسبه می‌شود. شبکه نمونه زیر را در نظر بگیرید:

شکل: یک شبکه نمونه

بیایید با محاسبه کوتاه‌ترین طول مسیر گره D شروع کنیم.

جدول زیر کوتاه‌ترین طول مسیر را از گره D به گره‌های دیگر در شبکه نشان می‌دهد.

جدول: کوتاه‌ترین طول مسیر از D تا هر گره دیگر در شبکه

میانگین این کوتاهترین طول مسیرها عبارتند از:

5. ضریب خوشه‌بندی

تا کنون، ما در مورد مرکزیت گره صحبت کرده‌ایم که نشان می‌دهد گره چقدر مهم است - اکنون می‌خواهیم در مورد ساختار محلی اطراف گره صحبت کنیم. وقتی می‌گوییم ساختار محلی، می‌خواهیم به اطراف نگاه کنیم و ویژگی‌های شبکه اطراف آن را مشخص کنیم. معیار کلاسیک این "ضریب خوشه‌بندی" که میزان اتصال همسایگان گره “v” را اندازه می‌گیرد. این نوع معیار می‌تواند برای مثال در یک شبکه اجتماعی مفید باشد. یعنی می‌گوید که چگونه ارتباطات من به دیگران متصل است.

از نظر ریاضی، ضریب خوشه‌بندی به صورت زیر نشان داده می‌شود:

معادله ضریب خوشه‌بندی یک گره v

در معادله بالا، e_v نشان دهنده ضریب خوشه‌بندی یک گره v است.

همانطور که در بالا توضیح داده شد، این معادله میزان اتصال همسایگان را اندازه می‌گیرد، یعنی دوستان (اتصالات) یک گره “v” چقدر به هم متصل هستند.

از نظر ریاضی با تعداد یال‌های بین گره‌های همسایه v تقسیم بر «k انتخاب 2» نشان داده می‌شود - k انتخاب 2 تعداد جفت‌هایی را که می‌توان از k شی مختلف شناسایی کرد (به عنوان مثال در یک مثال شبکه اجتماعی، تعداد جفت اتصالات ممکن). موارد فوق را می‌توان از طریق مثال نشان داده شده در زیر روشن کرد:

مثال 1:

شکل: مثال 1 محاسبه ضریب خوشه‌بندی

در اینجا گره “v” دارای اتصالات A، B، C، D است. اتصالات احتمالی بین گره‌های A، B، C، D عبارتند از: A-B، A-C، A-D، B-C، B-D، C-D (در مجموع: 6)

از شکل بالا مشاهده می‌شود که: : A-B، A-C، A-D، B-C، B-D، C-D متصل هستند.

بنابراین، در مثال بالا:

یعنی: تعداد یال‌های همسایگی به تعداد یالرهایی که در واقع رخ می‌دهد.

مثال 2:

شکل: مثال 2 از محاسبه ضریب خوشه‌بندی

باز هم اینجا:

در اینجا گره “v” دارای اتصالات A، B، C، D است. اتصالات احتمالی بین گره‌های A، B، C، D عبارتند از: A-B، A-C، A-D، B-C، B-D، C-D (در مجموع: 6)

از شکل بالا مشخص است که: : A-B، A-C، A-D، متصل هستند.

بنابراین، در مثال بالا:

بنابراین معیار ضریب خوشه‌بندی همیشه بین 0 و 1 است. 0 نشان می‌دهد که هیچ یک از اتصالات/دوستان شما متصل نیستند و 1 نشان می‌دهد که همه اتصالات/دوستان شما به یکدیگر متصل هستند.

از مفهوم ضریب خوشه‌بندی می‌توان گفت که ضریب خوشه‌بندی در واقع به ما می‌گوید که چند سه قلو گره همانطور که در شکل زیر نشان داده شده است. [متریک ضریب خوشه‌بندی یک مفهوم بسیار مهم در شبکه‌های اجتماعی است که در آن اگر (بگوییم) یک اتصال لینکدین به نام X داشته باشم و اگر X و Y متصل باشند، ممکن است به Y نیز متصل شوم. زیرا هم I و هم Y به عنوان اتصالات درجه دوم ظاهر می‌شوند و شبکه‌های اجتماعی مانند لینکدین چیزی را که نتیجه ضریب خوشه‌بندی است نشان می‌دهد].

شکل: ضرایب خوشه‌بندی که نشان می‌دهد چند مثلث وجود دارد

6. گرافلت‌ها

گرافلت‌ها مفهوم ضریب خوشه‌بندی را تعمیم می‌دهند. در ضریب خوشه‌بندی مشاهده کردیم که می‌توان تعداد مثلث‌های اطراف یک گره را شمارش کرد که مفهوم مهمی را در شبکه‌های اجتماعی تشکیل می‌دهد. گرافلت‌ها این مفهوم را تعمیم می‌دهند، زیرا به آنها اجازه می‌دهند تا انواع دیگر شکل‌ها را مانند شکل زیر بشمارند:

§         2 گره گرافلت

§         3 گره گرافلت

§         4 گره گرافلت

§         ….

شکل: گرافلت‌های 2، 3 و 4 گره

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

·         ما یک گرافلت برای 2 گره داریم.

·         3 گرافلت ممکن برای 3 گره وجود دارد.

·         و غیره…

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

بنابراین، می‌توانیم به صورت زیر فکر کنیم:

۱. درجه گره تعداد لبه‌هایی را که گره لمس می‌کند می‌شمارد.

۲. ضریب خوشه‌بندی تعداد مثلث‌هایی را که یک گره لمس می‌کند، شمارش می‌کند.

۳. بردار درجه گرافلت تعداد گراف‌ها (زیرگراف‌ها) را که یک گره لمس می‌کند، شمارش می‌کند.

7. نتیجه‌گیری از بخش‌های فوق:

از بحث بالا می‌توان گفت که راه‌های مختلفی برای به دست آوردن ویژگی‌های گره در گراف وجود دارد. آنها را می‌توان اینگونه توصیف کرد:

·         ویژگی‌های مبتنی بر اهمیت: 1) درجه گره. 2) معیارهای مختلف مرکزیت گره.

·         ویژگی‌های مبتنی بر ساختار: 1) درجه گره 2) ضریب خوشه‌بندی 3) بردار شمارش گرافلت.

به طور واقع بینانه، ویژگی‌های مبتنی بر اهمیت در پیش‌بینی میزان اهمیت یا تأثیرگذاری گره‌ها در یک گراف استفاده می‌شود که چندین مورد استفاده دارد مانند:

الف) شناسایی کاربران مشهور در شبکه‌های اجتماعی

ب) شناسایی معاملات متقلبانه

ج) و غیره

در حالی که:

ویژگی‌های مبتنی بر ساختار که ویژگی توپولوژی همسایگی اطراف یک گره را به تصویر می‌کشند، مانند: درجه گره، ضریب خوشه‌بندی، بردار درجه گرافلت برای توصیف ساختار شبکه در اطراف یک گره مفید است.