Analysis of feature pattern mining approaches on social network: A case study on Facebook

Abstract

Pattern mining algorithms obtain patterns frequently seen in a database and complex graphs which are available from gene networks to social networks. Complex graphs contain lots of valuable information on their nodes or edges. For this reason, pattern mining algorithms can be used to extract data from complex networks. However, these algorithms usually work on the graphs whose nodes have a single label. If these algorithms are implemented on multi labeled (multi-attributed) complex graphs, their complexities belong to NP-Complete. For this reason, in this study, different approaches have been evaluated to find patterns. The goal is to understand related methods and algorithms with their pros and cons to obtain common feature patterns from multi-attributed complex graphs. We also selected Facebook social network complex graph data set (SNAP - Stanford University FaceBook anonymized data set) as an application domain and we analyzed the most frequent feature patterns on friendship relations.

Günümüzde, kompleks çizgeler gen ağlarından sosyal ağlara kadar her alanda bulunmaktadır. Kompleks çizgeler diğer yapılara göre daha fazla veri içerdiğinden, kompleks çizgelerin madenciliği sonucunda daha anlamlı ve değerli bilgiler elde edilebilir. Bu çalışmada kompleks çizgelerden ortak özelliklere sahip örüntüler elde edilmek istenmiştir. Örüntü madenciliği algoritmaları bir veritabanından sıklıkla görülen örüntülerin elde edilmesini sağlar. Bu nedenle kompleks ağlardan veri elde edebilmek için örüntü madenciliği algoritmaları kullanılabilir. Ancak bu algoritmalar genellikle düğümleri tek etikete sahip olan çizgeler üzerinde çalışmaktadır. Bu algoritmalar, sosyal ağ çizgeleri gibi çok etiketli kompleks çizgelere uygulandığında maalesef algoritmaların karmaşıklık derecesi NP-tam sınıfına ait olmaktadır. Bu nedenle, bu çalışma kapsamında ilgili çizge algoritmaları, çizgenin veri setlerine dönüştürülmesi ve dönüşüm sonrası oluşturulan data setinde standart desen bulma algoritmalarının kullanılması gibi yöntemler incelenmiştir. Bu yöntemler güçlü ve zayıf yönleri ile, çok etiketli kompleks çizgelerinde desen analizi hedefi için değerlendirilmiştir. Bu çalışma sürecinde, uygulama alanı olarak Facebook SNAP veri seti kullanılmış, arkadaşlık ilişkilerinde en yüksek sıklıkla görülen ortak etiket deseni araştırılmıştır.