Gürkan Özsoy Blog
Tamamen Kişisel
Yeni algoritma karmaşık ağlar için grafik madenciliğini geliştiriyor
Virginia Üniversitesi Mühendislik ve Uygulamalı Bilimler Fakültesi profesörü Nikolaos Sidiropoulos, yeni bir hesaplama algoritması geliştirerek grafik madenciliğinde bir çığır açtı.
Sosyal medya bağlantıları veya biyolojik sistemler gibi ağları analiz etme yöntemi olan grafik madenciliği, araştırmacıların farklı unsurların nasıl etkileşime girdiğine dair anlamlı kalıpları keşfetmelerine yardımcı oluyor. Yeni algoritma, dolandırıcılık tespiti, hesaplamalı biyoloji ve veri analizi gibi alanlarda kritik öneme sahip bir sorun olan, büyük ağlarda üçgen-yoğun alt grafikler olarak bilinen sıkı bağlantılı kümeleri bulma konusunda uzun süredir devam eden zorluğu ele alıyor.
IEEE Transactions on Knowledge and Data Engineering dergisinde yayınlanan araştırma, Belçika’daki KU Leuven’de elektrik mühendisliği yardımcı doçenti olan ve daha önce UVA’da araştırmacı bilim insanı olarak görev yapan Aritra Konar’ın liderliğindeki bir işbirliğinin ürünüdür.
Grafik madenciliği algoritmaları genellikle sosyal medyada sıkça iletişim kuran iki kişi gibi bireysel nokta çiftleri arasındaki yoğun bağlantıları bulmaya odaklanır. Ancak araştırmacıların Triangle-Densest-k-Subgraph problemi olarak bilinen yeni yöntemi, bağlantı üçgenlerine (her bir çiftin bağlantılı olduğu üç noktadan oluşan gruplar) bakarak bir adım daha ileri gidiyor. Bu yaklaşım, birbirleriyle etkileşim halinde olan küçük arkadaş grupları veya biyolojik süreçlerde birlikte çalışan gen kümeleri gibi daha sıkı örülmüş ilişkileri yakalar.
Elektrik ve Bilgisayar Mühendisliği Bölümü’nde profesör olan Sidiropoulos, “Yöntemimiz sadece tek bağlantılara bakmıyor, aynı zamanda daha karmaşık ağları anlamak için çok önemli olan üç unsurdan oluşan grupların nasıl etkileşime girdiğini de dikkate alıyor” dedi. “Bu sayede devasa veri kümelerinde bile daha anlamlı örüntüler bulabiliyoruz.”
Üçgen yoğun alt grafları bulmak özellikle zordur çünkü geleneksel yöntemlerle verimli bir şekilde çözülmesi zordur. Ancak yeni algoritma, önemli ayrıntıları kaybetmeden çözmeyi daha hızlı hale getirmek için sorunu yeterince basitleştiren akıllı bir kısayol olan submodüler gevşeme denilen şeyi kullanıyor.
Bu buluş, bu daha derin, çoklu bağlantı ilişkilerine dayanan karmaşık sistemleri anlamak için yeni olanaklar sunuyor. Alt grupların ve örüntülerin bulunması, dolandırıcılıktaki şüpheli faaliyetlerin ortaya çıkarılmasına, sosyal medyadaki topluluk dinamiklerinin belirlenmesine veya araştırmacıların protein etkileşimlerini veya genetik ilişkileri daha hassas bir şekilde analiz etmelerine yardımcı olabilir.
Daha fazla bilgi: Aritra Konar et al, Mining Triangle-Dense Subgraphs of a Fixed Size: Hardness, Lovasz extension and ´ Applications, IEEE Transactions on Knowledge and Data Engineering (2024). DOI: 10.1109/TKDE.2024.3444608