Efficient analysis of large-scale social networks using big-data platforms

Abstract

Son yıllarda zengin içerikli çok büyük ağlardaki artış kompleks/sosyal ağ analizine dönük ilgiyi yeniden artırmıştır. Söz konusu analizler bir taraftan büyük çapta sosyal etkileşimleri anlamayı mümkün kılarken diğer taraftan O(n) üzeri kompleksitiye sahip algoritmalara dayalı önceki çalışmalarda sorun oluşturmaktadır. Bu tez önemli parametrelerini ve özelliklerini etkin ve verimli bir şekilde bulmak amacıyla büyük veri platformu kullanarak çok büyük ölçekli sosyal ağları analiz eder. Mobil telefon kullanımının popülerleşmesi ile birlikte telekomünikasyon ağları sosyal bağlayıcı ortamlara dönüşmüştür ve araştırmacıların sosyal etkileşimleri çok büyük ölçekte analiz etmesine olanak sağlamıştır. Derece dağılımları sosyal ağların en önemli karakteristikleri arasında yer alır ve büyük ölçekli sosyal ağlarda derece karakteristiği ile yapısal özellikleri araştırmak için biz bu tezde öncelikle tera-ölçekli bir telekomünikasyon arama detay kaydı veriseti derledik. Biz bu veriyi kullanarak bazı istatistik modelleri ülke çağrı çizgesi derece dağılımına karşı deneysel olarak değerlendirdik ve literatürdeki /enquote{power-law en iyi modeldir} iddalarına karşın, Pareto log-normal dağılımının en iyi uyumu sağladığına karar verdik. Ayrıca, sosyal ağlarda derece dağılımını yöneten parametreleri anlamak amacıyla, ağ operatörünün, büyüklüğünün, yoğunluğunun ve lokasyonunun derece dağılımını nasıl etkilediğini sorgulayıp ve cevap elde ettik.Yapısal özellik analizi dışında, bir sosyal ağda farklı konularda çok bağlantılı alt ağları bulmak için yapılan topluluk tespiti çalışmaları pratikte büyük ilgi çekmektedir. Çizge teorisinde, $k$-core çizgenin `yoğun' alanları olarakta bilinen çok bağlantılı alt çizgelerin tespiti için kullanılan anahtar bir ölçüttür. Sosyal ağ çizgeleri gibi gerçek dünya çizgeleri boyut yönünden büyüyüp, içerik yönünden zenginleşip ve topolojiler dinamik olarak değiştikçe, yalnız k-core altçizgesini bir defalığına hesaplama problemi ile değil ayrıca bunu dinamik değişikliklere göre güncel tutma problemi ile karşılaştık. Bu zorluklar bize yatay ölçeklenebilir saklama ve hesaplama platformu üzerinde $k$-core görüntü hesaplama ve sürdürme amaçlı bir takım algoritmalar önerme konusunda esin vermiştir. önerdiğimiz algoritmaların deneysel değerlendirme sonuçları bütün yeniden hesaplama yaklaşımına göre aşamalı ve yığın olarak $k$-core sürdürme avantajı ile birlikte birkaç basamak hızlandırma göstermiştir.Bununla birlikte, topluluğa katılımın yoğunluğu birçok seviyede seçilebilir ki bu da zamanla sürdürülmesi gerekli çok-çözünürlüklü topluluk gösterimini sonuç doğurur. Bu nedenle biz ayrıca çoklu-$k$-core çizgesi hesaplayıp sürdürecek Apache HBase ölçeklenebilir büyük-veri platformunda uygulanmış dağıtık algoritmalar önerdik. Deneysel değerlendirme sonuçları aşamalı çoklu-$k$-core sürdürmenin bütün yeniden hesaplamaya göre birkaç basamak hızlandırma sağladığını göstermiştir. Diğer taraftan, dağıtık çizge işleme amaçlı tasarlanmış bir çizge-bilinçli önbellek sistemi önerdik. Deney sonuçları geleneksel LRU bazlı sistemlerle karşılaştırıldığında 15 kata kadar hızlanma göstermiştir.

In recent years, the rise of very large, rich content networks re-ignited interest to complex/social network analysis at the big data scale, which makes it possible to understand social interactions at large scale while it poses computation challenges to early works with algorithm complexity greater than O($n$). This thesis analyzes social networks at very large-scales to derive important parameters and characteristics in an efficient and effective way using big-data platforms. With the popularization of mobile phone usage, telecommunication networks have turned into a socially binding medium and enables researches to analyze social interactions at very large scales. Degree distribution is one of the most important characteristics of social networks and to study degree characteristics and structural properties in large-scale social networks, in this thesis we first gathered a tera-scale dataset of telecommunication call detail records. Using this data we empirically evaluate some statistical models against the degree distribution of the country's call graph and determine that a Pareto log-normal distribution provides the best fit, despite claims in the literature that power-law distribution is the best model. We also question and derive answers for how network operator, size, density and location affect degree distribution to understand the parameters governing it in social networks.Besides structural property analysis, community identification is of great interest in practice to learn high cohesive subnetworks about different subjects in a social network. In graph theory, $k$-core is a key metric used to identify subgraphs of high cohesion, also known as the `dense' regions of a graph. As the real world graphs such as social network graphs grow in size, the contents get richer and the topologies change dynamically, we are challenged not only to materialize $k$-core subgraphs for one time but also to maintain them in order to keep up with continuous updates. These challenges inspired us to propose a new set of distributed algorithms for k-core view construction and maintenance on a horizontally scaling storage and computing platform. Experimental evaluation results demonstrated orders of magnitude speedup and advantages of maintaining $k$-core incrementally and in batch windows over complete reconstruction approaches.Moreover, the intensity of community engagement can be distinguished at multiple levels, resulting in a multiresolution community representation that has to be maintained over time. We also propose distributed algorithms to construct and maintain a multi-$k$-core graphs, implemented on the scalable big-data platform Apache HBase. Our experimental evaluation results demonstrate orders of magnitude speedup by maintaining multi-$k$-core incrementally over complete reconstruction. Furthermore, we propose a graph aware cache system designed for distributed graph processing. Experimental results demonstrate up to 15x speedup compared to traditional LRU based cache systems.