Tez No	İndirme	Tez Künye	Durumu
485241		Homojen ve heterojen evrimsel sosyal ağlarda bağlantı tahmini / Link prediction in evolving homogeneous and heterogeneous networks Yazar:ALPER ÖZCAN Danışman: PROF. DR. ŞULE ÖĞÜDÜCÜ Yer Bilgisi: İstanbul Teknik Üniversitesi / Fen Bilimleri Enstitüsü / Bilgisayar Mühendisliği Ana Bilim Dalı / Bilgisayar Mühendisliği Bilim Dalı Konu:Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrol = Computer Engineering and Computer Science and Control Dizin:	Onaylandı Doktora Türkçe 2017 140 s.
Karmaşık Evrimsel Ağlar, biyokimyasal ve ekolojik sistemlere kadar uzanan çeşitli alanlarda örnekleri olan ve zaman içinde dinamik bir şekilde topolojisi değişen ağlar olarak tanımlanmaktadır. Karmaşık ağlardaki zamana göre değişim "düğümlerin eklenmesi ve kaybolması", "düğüm çiftleri arasında bağlantıların eklenmesi ve kaybolması", "düğüm özelliklerinin değişmesi" olmak üzere üç farklı şekilde gerçekleşebilir. Kendi içinde karmaşık bir organizasyonu olan bu ağlarda, zaman içinde düğümlerin ve düğümler arasındaki bağlantıların değişim verisinin analizi, statik ağların analizine göre önemli bilgiler sağlamaktadır. Karmaşık ağlar doğada ve toplumda var olan çeşitli sistemleri betimlemektedir; protein ağları, İnternet, bilimsel işbirliği ağları, arkadaşlık ağları karmaşık ağlara örnek olarak verilebilir. Karmaşık Ağlar, halen çok sayıda bilinmeyenin olduğu ve son yıllarda sıklıkla üzerinde çalışılan bir alandır. Karmaşık Ağların bir alt alanı olan Sosyal Ağlarda düğümler sosyal alandaki öğeleri, aralarındaki bağlantılar ise bu öğeler arasındaki etkileşimi temsil etmektedir. Sosyal ağlar homojen ve heterojen olmak üzere iki farklı türe ayrılmaktadır. Homojen ağlar, aynı tür düğümlerin bulunduğu ve bu düğümler arasındaki bağlantıların aynı türde olduğu ağlardır. Heterojen ağlar ise farklı tür düğümler ve farklı tür bağlantılar içerdiği için homojen ağlara göre çok daha zengin bilgi içerirler. Yapıları daha karmaşık olduğu için modellenmeleri homojen ağlara göre daha zordur. Bağlantı tahmini problemi, ağ topolojisi, çeşitli benzerlik ölçütleri ve düğüm içeriği kullanılarak düğümler arası bağlantıların varlığının tahmin edilmesini amaçlamaktadır. Literatür çalışmalarında statik ve zamansal (dinamik) olmak üzere iki tip bağlantı tahmini problemi bulunmaktadır. Bağlantı tahmini probleminde yeni bağlantıların oluşup oluşmayacağı ve mevcut bağlantıların ileriki zaman dilimlerinde devam edip etmeyeceğinin tahmin edilmesi gerekmektedir. Homojen ağlarda zaman etkisini kullanan çeşitli çalışmalar yapılmış olmasına rağmen, evrimsel heterojen ağlarda zamanla değişim bilgisini kullanan yöntemler yetersiz sayıdadır. Bunun nedeni, heterojen evrimsel ağların kompleks yapısı, içermiş olduğu zengin bilgi ve zaman bilgisinin etkin kullanımının zor olmasıdır. Heterojen ağlarda, ağı oluşturan düğümlerin ve bağlantıların karşılıklı olarak sürekli bir etkileşim içinde olduğu karmaşık yapı; topolojik yapıyı oluşturan değişkenlerin tek denklemli modeller yerine eşanlı denklem sistemleri ile incelenmesi gereğini ortaya koymaktadır. Günümüzde homojen ve heterojen ağların zaman içinde değişimi ile ilgili çalışmalar henüz yeterli değildir. Ağların zaman içinde sürekli değişim eğiliminde olması ve düğümler arasındaki ilişkilerin çok dinamik olması nedeniyle zamanla değişim bilgisi çok önemli veriler içermektedir bu nedenle zamana göre değişim bilgisinin dikkate alınması çok önemlidir. Tez çalışması kapsamında, homojen ve heterojen evrimsel sosyal ağlar için zaman içinde değişim analiz edilmiş ve bağlantı tahmini için aşağıda belirtilmiş olan yeni yöntemler geliştirilmiştir. Homojen evrimsel ağlarda VAR (Vector AutoRegression) çok değişkenli zaman serisi modeli kullanılarak düğümler arasındaki bağlantıların tahmin edilmesi: Tez çalışmasının ilk önemli katkısı, zamanla değişim bilgisi kullanılarak evrimsel homojen ağlarda düğümler arasındaki bağlantıların tahmin edilmesidir. Önerilen çok değişkenli zaman serisi modeli ile evrimsel homojen ağlarda geçmişte ortaya çıkan düğümler arasındaki benzerlik skorları ve bu düğümler arasında meydana gelen bağlantılar eş zamanlı modellenerek, gelecekte hangi düğümler arasında bağlantı meydana geleceğinin tahmin edilmesi sağlanmıştır. Zamanla ilişkili olarak tanımlanan iki veya daha fazla değişken ile ilgili yapılan ölçümleri, zamana göre sıralanmış olarak gösteren serilere "çok değişkenli zaman serisi" denir. Çok değişkenli zaman serilerine girdi olarak, düğümler arası benzerlik ölçüt skorları ve düğümler arasındaki bağlantılar kullanılmış ardından gelecekteki benzerlik ölçüt skorları tahmin edilmiştir. Yöntemin ilk aşamasında veri kümelerinin farklı ardışıl zaman dilimlerindeki görüntüleri oluşturulmuştur. Ardından, her zaman dilimindeki ağ görüntüsü için düğümler arasında çeşitli ağırlıklı ve ağırlıksız benzerlik ölçüt skorları hesaplanmıştır. Farklı zaman dilimlerinde hesaplanan benzerlik ölçüt skorları ve bağlantı sıklık bilgisi çok değişkenli zaman serisi modeli olan VAR modeline girdi olarak verilerek gelecekteki benzerlik skorları tahmin edilmiştir. Bir diğer önerilen modelde de birden fazla benzerlik ölçüt skoru VAR modeli ile eşzamanlı modellenmiş ve farklı benzerlik ölçütlerin dinamik ilişkilerini kullanan bir model tasarlanmıştır. Ardından, gelecekteki benzerlik ölçüt skorları tahmin edilmiştir. VAR modeli, sistemde yer alan çok sayıda değişkenin geçmiş değerleri ile ifade edildiği ve her bir denklemin en küçük kareler ile çözümlendiği bir çözüm tekniğidir. Geçmiş bilginin kullanılması ile sağlanan bu yapı zaman serilerine dinamiklik katarak, birden fazla zaman serisi arasındaki ilişkileri yorumlama konusunda bir açılım yaratmıştır. Yöntemin son aşamasında, tahmin edilen benzerlik skorları kullanılarak tahmin etme başarımı, AUC cinsinden hesaplanmıştır. Önerilen modeller tek değişkenli zaman serisi modelleri ve statik bağlantı tahmini algoritmaları ile karşılaştırılmış ve daha başarılı sonuçlar verdiği görülmüştür. Heterojen evrimsel ağlarda VAR çok değişkenli zaman serisi modeli kullanılarak düğümler arasındaki bağlantıların tahmin edilmesi: Tez çalışmasının ikinci katkısı, zamanla değişim bilgisi kullanılarak evrimsel heterojen ağlarda düğümler arasındaki farklı türlere ait bağlantıların tahmin edilmesidir. Önerilen çok değişkenli zaman serisi olan VAR modeli ile heterojen ağın farklı zamanlardaki görüntülerinde hesaplanan çeşitli ağırlıklı ve ağırlıksız benzerlik ölçüt skorları ve bağlantı sıklık bilgisi eşzamanlı modellenmiş ve bütün bağlantı türlerine ait gelecekteki benzerlik ölçüt skorları tahmin edilmiştir. Gerçeklenen model ile zaman bilgisinin etkin şekilde kullanılması, tahmin edilecek bağlantının gözlenmiş olması kabulünün ortadan kaldırılması, düğüm çiftleri arasındaki bağlantıların ve benzerlik ölçütlerinin korelasyonunun kullanılması gerçeklenmiş ve mevcut heterojen bağlantı tahmini yöntemlerinin eksikliklerinin giderilmesi sağlanmıştır. Bağlantı tahmini için VAR modeline girdi olarak farklı bağlantı türleri için hesaplanan benzerlik skorları ve bağlantı sıklık bilgisi verilerek zaman içindeki değişimleri eşanlı ele alınmıştır. Bir diğer önerilen modelde de en iyi sonucun elde edildiği lokal (komşuluk tabanlı) ölçütler ve global (tüm yolların birleşimini temel alan) ölçütler bütün bağlantı türleri için eşzamanlı modellenmiş ve farklı benzerlik ölçütlerin dinamik ilişkilerini kullanan bir model tasarlanmıştır. Önerilen modeller her bağlantı türününün ayrı olarak ele alındığı tek değişkenli zaman serisi modelleri ile karşılaştırılmış ve daha başarılı sonuçlar verdiği görülmüştür. Heterojen evrimsel ağlarda NARX çok değişkenli sinir ağı modeli kullanılarak düğümler arasındaki bağlantıların tahmin edilmesi: Tezin son aşamasında, zamanla değişen heterojen sosyal ağlarda, geçmişte ortaya çıkan düğümler arasında meydana gelen farklı türlü bağlantılar ve düğümler arası benzerlik ölçütlerinin zaman içindeki değişimlerinin eşanlı kullanıldığı NARX (Doğrusal Olmayan Otoregresif Dışsal) sinir ağı modeli önerilmiş ve gerçeklenmiştir. VAR çok değişkenli zaman serisi modelinden farklı olarak NARX modeline girdi olarak farklı bağlantı türleri için hesaplanan benzerlik skorları ve bağlantı sıklık bilgisindeki değişimler verilerek eş zamanlı olarak ele alınmıştır. Girdi olarak verilen bağlantı sıklık bilgisindeki değişimler, ilgili bağlantı türü için ardışıl zaman aralıklarında iki düğüm çifti arasındaki bağlantının ağırlığının azalması durumunda "kopan bağlantı sayısı", bağlantının ağırlığının artması durumunda "oluşan bağlantı sayısı", bağlantının ağırlığının korunması durumunda "korunan bağlantı sayısı" bilgilerinden oluşmaktadır. NARX modeli iki katmanlı ileri beslemeli, döngülü ve dinamik ağlar olup zaman serisi tahminlerinde sıklıkla uygulama alanı bulmaktadır. Dinamik ağlar gecikme ve döngü mekanizmalarına sahip olmaları sebebiyle, sıralı ve zamana göre değişen veriler üzerinde kullanılabilmekte ve zaman serileri problemlerinde daha çok tercih edilmektedir. NARX modelinin bir avantajı, zaman serisi modellerinde olduğu gibi serinin durağan olmasını önşart olarak kabul etmemesi ve durağan olmayan seriler üzerinde de öngörü yapabilmesidir. Bir diğer avantajı da yine zaman serisi modellerinde olduğu gibi seriyi oluşturan veriler arasında doğrusal bir ilişkinin olduğunu varsaymaması ve hem doğrusal hem de doğrusal olmayan ilişkileri modelleyebilmesidir. Gerçeklenen modelde ayrıca NARX sinir ağındaki bağlantı ağırlıkları kullanılarak girişler arasındaki göreceli önem dereceleri heterojen ağdaki farklı bağlantı türleri için belirlenmiştir. Gerçeklenen model ile mevcut statik heterojen bağlantı tahmini yöntemlerinin eksiklikleri olan zaman bilgisinin etkin şekilde kullanılamaması ve zaman serisi kullanan modellerin eksiği olan tahmin edilecek bağlantının gözlenmiş olması kabulünün giderilmesi sağlanmıştır. Önerilen yöntemler iki farklı veri kümesi üzerinde test edilmiştir. Veri kümeleri, DBLP bilgisayar bilimleri bibliyografik veri kümesi ve Delicious sosyal sık kullanılanlar veri kümesinden oluşmaktadır. Veri kümeleri öğrenme ve test kümelerine ayrılmış ve öğrenme kümesi zaman serisi modellerini oluşturmak için test kümeside modellerin başarımını ölçmek için kullanılmıştır. Dengesiz veri kümelerinde de iyi sonuç vermesi nedeniyle başarımı ölçmek için AUC kullanılmıştır. Tanımlanan çeşitli AUC ölçümleri ile yöntemlerin farklı koşullardaki başarımı ölçülmüştür. Son üç zaman diliminde bağlı olmayan düğüm çiftleri için AUCdisconn, son üç zaman diliminde bağlı olan düğüm çiftleri için AUCconn, son zaman diliminde bağlı olmayan düğüm çiftleri için AUClastDisconn ve son zaman diliminde bağlı olan düğüm çiftleri için de AUClastConn değerleri hesaplanarak bağlantı tahmini yöntemleri değerlendirilmiştir. Kullanılan 4 farklı AUC ölçümlerine ilaveten, son zaman diliminin ardından bağlı-bağlı değil veya bağlı değil-bağlı şeklinde bağlılık durumunda değişiklik olan düğüm çiftleri için ise AUCchange hesaplanmıştır. Önerilen yöntemler paralel algoritmalar tasarlanarak dağıtık ortamlarda karmaşıklığı azaltılabilir ve büyük ağlarda kullanılabilir. Ayrıca farklı tür benzerlik skorları ve farklı veri kümeleri üzerinde test edilerek genişletebilir.
Complex Evolving Networks are described as networks whose topology change dynamically over time. These networks structures have examples in various areas extending from biochemical to ecological systems. Temporal changes in complex networks can actualize in three different ways including "addition and removal/disappearance of nodes", "addition and removal of links between node pairs" and "modification of node properties/attributes". In complex networks which have a complex organization, the analysis of variance information of nodes and links over time provides vital information compare to the analysis of the static networks. Complex networks delineate various systems existing in nature and society. Protein networks, Internet, scientific collaboration networks, and social/friendship networks can be given as examples for these type of networks. Complex Networks are an area which have still many unknowns and have been frequently studied in recent years. Nodes represent elements in social area and links among these nodes represent interaction between the elements in Social Networks which is a subfield of Complex Networks. Social networks are divided into two substantial categories: homogeneous and heterogeneous social networks. Homogeneous networks include same type of nodes and same type of links between nodes. On the other hand, heterogeneous networks consist of different type of nodes and links, and for this reason; they contain much more rich data compare to the homogeneous networks. Thus, modeling heterogeneous networks is more difficult than modeling the homogeneous networks because of their complex nature. The problem of the link prediction aims to predict the existence probability of a links between node pairs by using network topology, various proximity (similarity) measures and node content information. In the literature, two related types of link prediction problems are considered: missing (static) and temporal (dynamic). In the case of the link prediction problem, it is necessary to estimate the prediction of both new links and repeated links. Although there are several link prediction studies in homogeneous networks using temporal information, there are very few methods available that employ time effect. The main reasons are representation difficulties of the complex structure, rich heterogeneous information, effective usage of influences between multi-typed relationships and the time effect. These characteristics of the evolving heterogeneous networks make link prediction a more challenging task. To overcome these difficulties, link prediction in such networks must model temporal evolution of the multi-typed topological features and link occurrences information of the network structure simultaneously. Consequently, link prediction in evolving heterogeneous networks must be modeled by simultaneous multivariate equations models instead of univariate models. Studies on evolving homogeneous and heterogeneous networks do not mature to a desired level yet. Due to the dynamicity of the network structure and multi-typed topological features, the usage of network evolution for link prediction contains crucial information. Thus taking into account of the changes of topological features over time is very important. In this thesis, we examine models for analysis of time varying information and link prediction models that combine the time information for evolving homogeneous and heterogeneous networks are implemented. Link Prediction method in evolving homogeneous network based on a VAR (Vector Autoregression) Model for Multivariate Time Series forecasting: The first major contribution of the Thesis is the utilization of the network temporal evolution for predicting links between node pairs. The novelty of our approach lies in the method by which we apply Multivariate Time Series model to combine topological similarity measures and temporal evolutions of link occurrences information simultaneously. That enables us to predict repeated link occurrences as well as to identify new link occurrences. A multivariate time series, which involves observation and analysis of more than one statistical variable, is observed in time order. The node similarities and node connectivity information for each pair of nodes in certain time periods are utilized as input to Multivariate Time Series and future similarity measure scores are forecasted. First of all, the network is split into several time-sliced snapshots in experiments, where each snapshot represents the states of the network at different times. Then, unweighted and weighted similarity measure scores between pairs of nodes are calculated for all time-sliced snapshots. A multivariate time series model (VAR) is built for each pair of nodes in consecutive snapshots. Finally, the combination of similarity measures scores and the link occurrences information for each pair are employed as an input to the VAR model then future scores are forecasted. As a second proposed approach, the combination of all similarity measures scores and the link occurrences information between node pairs are used simultaneously and future score values are estimated. VAR is a multiple time series model in which each variable is expressed as a linear function of its own past values. The past values of the remaining variables and each equation coefficients may be estimated separately by ordinary least squares. This superior model provides a systematic way to capture rich dynamics and inter dependencies among multiple time series. In the last stage, the prediction performance in terms of AUC is evaluated on the test set by using the estimated similarity scores. The proposed models outperform the baseline static and univariate time series methods according to the comparison result. Link Prediction method in evolving heterogeneous network based on a VAR Model for Multivariate Time Series forecasting: The second contribution of the Thesis is the proposal of a novel method to solve the problem of link prediction in evolving heterogeneous networks composed of multiple types of nodes and links that change over time and investigate the dynamics of multi-typed links in a heterogeneous social networks. The proposed model based on Multivariate Time Series (VAR) in evolving heterogeneous networks integrates the unweighted and weighted similarity measures scores and link occurrences information and future score values are estimated for all link types. Our implemented model employs the network temporal information, removes the assumption of past existence of a connection which is to be estimated and uses the correlations between multi-typed relationships and similarity measures. Thus, proposed method resolves drawbacks of the existing heterogeneous link prediction methods. The calculated node similarity scores and node connectivity information of node pairs for multi-typed relationships are used as input to Multivariate Time Series and the variation of similarity scores and temporal evolutions of link occurrences are analyzed simultaneously. As a second proposed approach, the combination of all best local (neighborhood-based) and global (path-based) similarity measures and link occurrence information for all link types are employed simultaneously and the model using dynamic relationships of multi-typed relationships is implemented. According to the comparison of the proposed models and temporal link predictors based on univariate time series methods, the proposed approaches outperform the baseline models. Link Prediction method in evolving heterogeneous network based on a multivariate model using the NARX Neural Network: The last contribution of the Thesis is the proposal of a novel method based on Nonlinear Autoregressive Neural Network with External Inputs (NARX) to integrate the temporal changes information for multi-typed links and the similarity measures between multi-typed links in evolving heterogeneous networks. Unlike the multivariate time series model (VAR), the calculated node similarity scores and the frequency of changes (e.g., the creation, preservation or removal of the link between node pairs) in the occurrence of links over consecutive time steps are used as input to NARX simultaneously. The frequency of changes in the occurrence of links include "Link Removal score" that demonstrates the decrease of weight value between the node pairs in the next time period, "Link Creation score" that represents the increase of weight value (increase in number of connections value) between the node pairs in the next time period and "Link Preservation score" that shows the weight value between the node pairs remaining unchanged in the consecutive time period. NARX is an implementation of recurrent dynamic networks with a two-layer feedforward network and is commonly used in time-series modeling. Due to the recurrent dynamic neural network models have feedback connections and the next value of the time series is regressed on previous values of the time series, these models are important for the forecasting of time series. Traditional time series methods require that the series to be stationary which means that the mean, variance and autocorrelation do not change over time. The other significant limitation is that traditional time series methods are only appropriate under the assumption that the time series are generated from linear processes, which is generally not accurate. NARX is a promising alternative to handle these major restrictions. NARX can reveal patterns adaptively from the time series data without prior assumption about the process from which a particular time series has generated. Hence, NARX efficiently models both linear and non-linear processes, stationary as well as non-stationary time series. Also, the proposed model determines the relative importance of each input variable based on connection weights for the corresponding link type in heterogeneous network. Our implemented model employs the network temporal information, removes the presumption of past occurrence of a connection which is to be estimated, and distinguish the nonlinear temporal evolution mechanisms of each link type simultaneously. Thus, proposed method resolves drawbacks of the existing heterogeneous link prediction methods. Proposed methods are evaluated on two longitudinal real-world heterogeneous datasets. These data sets are; bibliographic dataset DBLP and a social bookmarking dataset Delicious. Each dataset is split into training and test sets such that training set contains time-sliced snapshots of the network that are used to create time series models and test set contains the actual links in the future. Due to the The Area Under Curve (AUC) is a commonly used performance measure in imbalanced datasets, our link prediction models are evaluated in terms of AUC. Distinct AUC measures are defined for comparing the performance of link prediction. AUCdisconn is defined for only non-connected pairs in the most recent three previous time periods in the training set, AUCconn is defined for only connected pairs in the most recent three previous time periods, AUClastDisconn is defined for only non-connected pairs in the last time period, AUClastConn is defined for only connected pairs in the last time period. Additionally, AUCchange is defined for only the pairs whose state (connected or non-connected) are altered to another state after the last time period which is one of the hardest task in link prediction. The proposed methods may be extended by designing the parallel computation methods in distributed environments to decrease the complexity and can be used in huge networks. Additionally, the proposed methods may be enhanced by using various types of node similarities and different types of network datasets.