Community Event Prediction In Evolving Social Networks

Abstract

Geçtiğimiz son on yıl internet ve web üzerinden elde edilen bilginin hızla ve çarpıcı bir biçimde artmasına tanıklık etmiştir. Sosyal ağlar kişisel bilgisayarlar, cep telefonları ve diğer donanımsal yenilikler gibi internet erişimli cihazların yaygınlaşmasıyla birlikte oldukça popüler hale gelmiştir. Sosyal ağ siteleri kullanıcılarına fikirlerini paylaşma, güncel durum ve yorumları yayınlama, yeni haberleri takip edebilme, arkadaşlar ve meslektaşlar ile iletişimde kalabilme gibi olanaklar sağlamaktadır. Çevrimiçi sosyal ağların hızlı gelişimi çok çeşitli senaryolarda ağ merkezli verilerin muazzam bir biçimde artmasına yol açmıştır. Birçok sosyal ağ çeşidinde veri, düğümlerin bireyleri, ayrıtların ilişki ve etkileşimleri temsil ettiği çizgelerden oluşur. Ağ yapısı içerisindeki bir düğüm kümesi, dışarıya olan bağlantı sayısına kıyasla kendi içinde daha fazla sayıda bağ içeriyor ise bu düğüm kümesi bir topluluk olarak nitelendirilebilir. Bu gibi sosyal ağlarda topluluklar, ağ elemanlarının birbirleriyle ilişki ve etkileşim kurması neticesinde oluşmaktadır. Topluluğun en yaygın tanımı şudur: topluluk içeride yoğun olarak birbirine bağlı ancak dışarıyla daha az yoğunlukta bağlantısı olan düğümler topluluğudur. Toplulukların belirlenmesi, düğüm veya ayrıt bazında bir yaklaşım sergilenen mikroskopik düzey ve bütün çizge yapısını ele alan makroskopik düzeyden farklı olarak, daha ara yapılar olan topluluklar kullanılarak, ağ yapısının mezoskopik düzeyde tanımlanmasıdır. Topluluk üyeleri zaman içinde birbirleriyle ve topluluk dışındaki ağ üyeleriyle etkileşim kurarak dinamik veya zamansal bir davranış sergilerler. Sonuç olarak, topluluklar belirli bir zaman diliminde kararlı bir biçimde durabilir, periyodik örüntü sergileyebilir, üye bileşiminde ansızın değişiklikler olabilir veya diğer başka dinamik davranışlar gösterebilirler. Bu nedenle toplulukların ve ağın zamansal değişimlerinin irdelenmesi önem arz etmektedir. Bu fenomen araştırmacıları bireyler arasındaki bağlantıların nasıl kurulduğu ve zamanla nasıl değiştiğini araştırma konusuna yöneltmiştir. Ağ yapılarının içerisinde yer alan bireyler/varlıklar arasındaki ilişkilerin çeşitli bilimsel metotlar aracılığı ile detaylı olarak incelenmesi sonucu elde edilen verilerden anlamlı sonuçlar türetilmesi Sosyal Ağ Analizi olarak tanımlanmaktadır. Bu bağlamda, topluluk dinamiklerinin gözlemlenmesi ve değişiminin öngörülmesi Sosyal Ağ Analizi'nin en önemli konularından biridir. Toplulukların değişimlerinin belirlenmesi, ağın içsel organizasyonundaki temek değişiklikleri tanımlamak açısından elzemdir. Toplulukların zaman içindeki değişiminin analiz edilmesi sosyoloji, kriminoloji, reklamcılık ve pazarlama, bilgi difüzyonu, öneri sistemleri gibi pek çok uygulama alanında genişçe yer almaktadır. Üyelerin gizli yönelimleri ve beğenileri, hangi toplulukların büyüyeceği veya küçüleceği gibi olayların anlaşılmasıyla açığa çıkarılabilir. Örnek olarak, topluluklara pazarlama faaliyeti yapmak ve bu faaliyetin zaman içinde sonuçlarını izlemek verilebilir. Buradan yapılan çıkarımlar daha sonra pazarlama teşviklerinin yeniden düzenlenmesinde kullanılabilir. Bir sosyal ağ sitesindeki kullanıcı yorumları ve arkadaşlık ilişkileri yeni fikir ve politik görüşlerin oluşumunu ve gelişimini izlemekte kullanılabilir. Toplulukların gelişimini takip eden yöntemler yaygın olarak topluluğun büyüme, birleşme veya yok olma gibi olaylarını tanımlayan çerçeveler üzerine kurulmuştur. Bunların birçoğu, toplulukların evrimini incelemek üzere iki adımlı olay eksenli modeller önermiştir. Bu modeller birincil olarak her bir zaman dilimine ait çizgelerin topluluklarını belirleme ve daha sonra ardışık zaman dilimlerindeki bölümlemeler arasındaki ilişkiyi kritik olaylar olarak tanımlamakta ve toplulukların yapısal özelliklerini öznitelik olarak kullanarak olayları tahmin etmektedir. Netice olarak bu yöntemler, bir sonraki adımdaki olayları bilinmeyen zaman dilimi de dahil olmak üzere tüm zaman dilimlerine ait çizgelerdeki toplulukların belirlenmesi ve bütün topluluksal özelliklerinin hesaplanmasını gerektirmektedir. Buna ek olarak, yakın zamandaki çalışmalar toplulukların evrimini çizgelere ait bütün tarihsel bilgileri kullanarak tahmin etmektedir. Ancak bu tarz bir yaklaşım, bütün geçmiş veriyi kullanması ve sadece ağ oluşumunun ilk aşamalarında var olmuş olan düğümleri diğerlerinden ayırt etmeksizin bütün düğüm ve ayrıtları eşit olarak göz önüne almasından mütevellit, güncel değişimle ilgili doğru sonuçlar sağlamakta başarısız olabilir. Bu tezde, toplulukların evrimsel dinamikleri irdelenmiş ve toplulukların gelecekteki olaylarını tahmin etmek amacıyla olay eksenli bir yaklaşım önerilmiştir. Dinamik ağ bir dizi statik zaman adımlı çizgeler olarak modellenmiş ve her bir zaman adımlı çizge belirlenen zaman aralığında veya o zamana kadar olan etkileşimlerden oluşturulmuştur. Her bir zaman adımında topluluklar belirlenmiş ve toplulukların yapısal ve zamansal nitelikleri hesaplanmıştır. Ele alınan özellikler toplulukların içsel ayrıt yapıları ve toplulukların ağın geri kalanıyla olan dışsal etkileşimlerini de içerecek şekilde pek çok niteliği kapsamaktadır. Ardışık zaman adımlarındaki her bir topluluk çifti için bir benzerlik ölçütü hesaplanmış ve önerdiğimiz olay belirleme algoritması uygulanarak anlamlı olaylar saptanmıştır. Daha sonra olay öngörüsü, tanımlanmış olayların sınıf etiketleri, yapısal ve zamansal topluluk niteliklerinin giriş parametresi olarak kullanıldığı bir sınıflandırma problemi olarak modellenmiştir. Detaylandırılmış deneysel sonuçlar önerilen olay öngörü modelinin topluluk olaylarını doğru olarak yakınsadığını ispatlamıştır. Tez kapsamında önerilen olay eksenli çerçeve kullanılarak, zamansal topluluklarda olayların öngörülmesinde karşılaşılan iki temel soruna da çözüm getirilmiştir. Tezin birinci katkısı; topluluk olaylarının zaman serisi analizi modelleri kullanılarak öngörülmesidir. Zaman serisi modelleri topluluksal niteliklerin bir sonraki zaman adımında nasıl değişeceğini ve değerinin ne olacağını tahmin ederek, toplulukların sıfırdan belirlenmesini önlemiş olur. Bir sonraki adımda olayları öngörülecek olan zaman dilimine ait toplulukların her biri için, biriken ve kayan pencereleme tekniklerine göre geçmişten günümüze topluluksal değerlerden müteşekkil bir zaman serisi oluşturulur. Bütün geçmiş veriyi işleyen biriken pencereleme tekniğinin aksine, kayan pencereleme tekniği dinamik ağın güncel durumu üzerine yoğunlaşır ve dolayısıyla ağdaki en son değişiklikleri meydana çıkarır. Zaman serilerinin oluşumu ve analizinde farklı pencere aralıkları test edilmiştir. İki adet gerçek veri üzerinde yapılan deneysel sonuçlar önerilen çerçevenin toplulukların nitelik değerlerinin makul bir hata oranı ile tahmin edildiğini ve öngörülen olayların gerçek olay etiketleriyle yüksek oranda örtüştüğünü göstermektedir. Buna ek olarak, pencere büyüklüğünün tahmin hatası ve olay öngürüsü üzerindeki etkisi irdelenmiştir. İkinci olarak, olayların öngörülmesinde başarılı sonuçlar üreten topluluksal nitelikler tespit edilmiştir. Ağın çeşitli yapısal niteliklerini hesaplayan ve topluluk gelişiminin gelecekteki doğrultusunu tüm topluluksal nitelikleri hesaplamadan, önde gelen topluluk nitelik alt kümesini tespit ederek öngören yeni bir çerçeve önerilmiştir. Önerilen çerçeve ağın yapısal niteliklerini kullanarak topluluk olay tahmininde doğru sonuç üretmeyi sağlayan topluluk nitelikleri alt kümesi belirlemektedir. Her bir zaman noktasında çok sayıda topluluksal niteliği hesaplayan yöntemlerin aksine, önerilen çerçeve ağ topolojisinden faydalanarak topluluğun gelecekte başına gelecek olayı en etkin biçimde öngören en kestirimci topluluksal nitelikleri bulmaktadır. Dört farklı gerçek veri seti üzerinde yapılan deneyler önerilen çerçevenin etkinliği doğrulamıştır. Yapılan deneyler, önerilen çerçevenin bütün nitelik kümesi kullanılarak üretilen öngörü sonuçlarıyla hemen hemen aynı sonuçlar ürettiğini, sonuçlar arasında istatistiksel bir farklılık bulunmadığını göstermiştir. Önerilen çerçeve ve bütün topluluk niteliklerinin kullanımı çalışma süresi ölçülerek karşılaştırılmış ve çerçevenin hızlandırma oranı sunulmuştur. Sonuçlar, önerilen çerçeve kapsamında daha az nitelik hesaplanmasından dolayı, aynı nispette hesaplama zaman ve maliyetinde düşüş olduğunu kanıtlamıştır.

The last decade has witnessed the dramatically quick and explosive growth of information available over the Web and Internet. Social networks have become very popular due to increasing proliferation of Internet enabled devices such as personal computers, mobile phones and other recent hardware innovations. Social networking sites enable users to share ideas, post updates and comments, to follow breaking news while keeping up with friends or colleagues. Rapid growth of online social networks has led to a tremendous explosion of network centric data in a wide variety of scenarios. Data from many types of social networks is a graph, where nodes represent individuals and edges represent the relationship and interactions among individuals. In such social networks, communities are constituted as a result of establishing relationships and interactions with each other. Although no single definition has been agreed upon, the most common definition of community is: a collection of nodes who are more densely connected to each other than with the rest of the network. Discovery of communities consists in characterizing the structure of a network at the mesoscopic level, i.e. neither the point of view of a single node or edge (microscopic level) nor the whole graph structure (macroscopic level), but rather an intermediary structure, namely community. Inherently, as time passes, community members interact with each other, but they also interact with others outside the community, resulting in a dynamic or temporal behavior. As a result, communities may stay stable just over a period of time, display a periodic pattern, change member composition abruptly, and perform many other evolutionary events. This phenomenon attracts researchers to study how connections between individuals are established and how they evolve over time. Capturing the community dynamics and predicting their evolution has been an important subject in Social Network Analysis (SNA). Quantifying community evolution is crucial to identify major changes in the internal organization of the network. Analyzing the evolution of communities over time provides insights in many application domains such as sociology, criminology, advertising and marketing, information diffusion, recommender systems, etc. Latent trends of members' behavior and adoption can be exposed by understanding which communities are growing, shrinking or undergo other events. For instance in marketing strategy, performing the marketing actions on communities and tracking the results of those actions over time is necessary to extract knowledge that can be used to support the redesign of marketing promotions. The user comments and friendship ties within a social networking site can be used to follow emergence and development of new ideas and political views. Common approaches to tracking the evolution of communities have devised on an event framework that defines a specific behavior of a community like growth, merge and disappear. Many of them propose a two-step event based model to explore community evolution which firstly detect communities on each snapshot graph and secondly construct relationships between partitions at successive snapshots defining critical events and predicting events by use of community features as attributes. These approaches need community extraction and computing the whole community features of each snapshot including the snapshot which its future to be predicted. Moreover, recent studies predict community evolution by considering the whole historical information. However, such an approach may fail to provide accurate results on current evolution since it considers all the historical data and treat all nodes and links equally, even if they only appear at the early stages of the network life. In the thesis, evolutionary dynamics of the communities has been studied and an event based approach proposed to predict future events of the communities. The dynamic network is modeled by a series of static snapshots and each snapshot corresponds to a time interval constituted of the interactions during/up to that specific interval. Communities in each snapshot are mined and communities' structural and temporal features are computed. The extracted features cover many properties of both the internal link structure and the external interaction of the community with the rest of the network. A similarity metric is calculated for each pair of communities at successive snapshots and significant events of the communities are identified by applying our proposed event detection algorithm. Then, event prediction modeled as a classification problem where identified events are used as class labels for the classifiers and the structural features as input parameters. Detailed experimental results have proved that the proposed event prediction model can accurately estimate community events. By utilizing the underlying event based framework, the thesis suggests frameworks to two substantial problems in event prediction of temporal communities. The first one is predicting community events by employing time series analysis models. A time series model predicts how particular community features will change in the following time period thus directly predicts community features at the next time step thus it avoids discovering communities from scratch. A time series is built for the last snapshot communities those the events will be predicted, recording the feature values of the matching communities from past to present using landmark and sliding window techniques. Unlike the landmark windows which take into consideration all the historical data, sliding windows focus on the most recent state of the dynamic network thus uncover the most recent changes occurring in the network. Distinct time window intervals are examined in constituting and analyzing time series. Experimental results on two real datasets show that the proposed framework forecasts community feature values with a reasonable error rate and predicted events highly overlap with the actual event labels. Moreover, the effect of window size on the forecast error and event prediction is uncovered. The second one is identification of community features that perform successful prediction results. A novel framework proposed to examine various structural features of the network and detects the most prominent subset of community features in order to predict the future direction of community evolution without computing the entire feature set. The framework extracts the network's structural properties and use it to determine the subset of community features that leads to accurate community event prediction. Unlike traditional approaches that harvest a large number of features at each time point, the proposed framework suggests the most predictive community features by exploiting the network's topology to effectively determine whether a community will remain stable or undergo certain events such as shrink, merge or split. Experiments conducted on four real datasets verified the effectiveness of the proposed framework. The experiments indicated that framework produces almost the same prediction results as those produced using the entire feature set, such that there is no statistical difference. Furthermore, the results for the running time and speed-up of framework over the use of all features have also presented. Due to the lower number of features that should be calculated, there is a corresponding reduction in computational time and cost.