Geri Dön

On balancing social networks

Sosyal ağların dengelenmesi

PDF İndir

  1. Tez No: 538796
  2. Yazar: ARANIYOS TEREFE WELDEGEBRIEL
  3. Danışmanlar: DR. ÖĞR. ÜYESİ BURAK YILDIRAN STODOLSKY
  4. Tez Türü: Doktora
  5. Konular: Matematik, Mathematics
  6. Anahtar Kelimeler: Belirtilmemiş.
  7. Yıl: 2019
  8. Dil: İngilizce
  9. Üniversite: İstanbul Teknik Üniversitesi
  10. Enstitü: Fen Bilimleri Enstitüsü
  11. Ana Bilim Dalı: Matematik Mühendisliği Ana Bilim Dalı
  12. Bilim Dalı: Matematik Mühendisliği Bilim Dalı
  13. Sayfa Sayısı: 72

Özet

Bu tezde, işaretli (+/-) tam çizgelerin optimizasyonunu incelenmektedir. Herhenagi bir işaretli çizgeyi, özellikte tam işaretli çizgeleri, dengleyen bir algoritma geliştirilmiştir. 1946'da, Heider bazı sosyal ağlarda bireyler arasındaki ilişkilerin değişmesinin zor olmasına rağmen diğer ağlarda bireyler arasındaki ilişkilerin kolaylıkla değiştiğini gözlemledi. Üç kişiden oluşan tüm ağları incelediğinde, bireylerinin hepsinin arasında arkadaşça ilişkiler olduğu zaman veya iki arkadaş ortak bir üçüncü kişiye düşman oldukları zaman bu ilişkilerin kalıcı olduğunu fark etti. Bu tür üç kişilik sosyal ağları dengeli üçlüler olarak tanımlarken, geri kalan üç kişilik ağları dengesiz üçlüler olarak tanımladı. Daha büyük sosyal ağlar içinse, eğer ağın içindeki bütün üçlüler dengeli ise ağın dengeli olacağını belirtti. Bu traihten sonra yapısal denge konusu üzerinde yapılan çalışmalarda üç önemli nokta üzerinde durulmuştur: İncelenen herhangi bir ağın dengeli olup olmadığının belirlenmesi, dengesiz ağlardaki dengeszilik miktarını ölçen ölçütlerin geliştirilmesi, ve tüm ağları dengeleyen algoritmaların geliştirilmesi ve bu algoritmaların gerçek sosyal ağlardaki dönüşümleri ne doğrulukta tahmin ettiklerinin irdelenmesi. Cartwright ve Harary, Heider'in gözlemlerinin işaretli çizgeler kullanılarak özetlenebileceğini gösterdi. Onlar {\em dengeli işaretli bir çizgeyi} her bir döngüsünün kenar işaretlerinin çarpımının pozitiv olduğu bir çizge olarak tanımladılar. Bununla birlikte, bu koşulun genel işaretli bir çizgede kontrol edilmesi oldukça zordur. Bu zorluğun üstesinden gelmek için Cartwright ve Harary, işaretli bir çizgenin dengeli olabilmesi için çizgenin düğüm kümesinin, her pozitiv kenar parçaların içinde ve her negatif kenar iki parça arasında kalacak şekilde, ikiye bölünmesi gerektiğini gösteren Yapı Teoremini kanıtladılar. Tabiiki bu kümelerden birisinin boş olma ihtimalini de belirttiler. Bu koşulu doğrulamak, döngü koşulundan daha kolaydır, çünkü Yapı Teoremi negatif kenarlar kümesinin iki parçalı (bipartite) bir çizge oluşturduğunu ima etmektedir ki bunu kontrol etmek kolaydır. Geriye kalan işlem positif kenarların parçalar içinde kalıp kalmadığını değerlendirmektir ve eğer böyle ise çizge dengelidir. İşaretli bir çizgedeki dengesizlik miktarını ölçmek için ise birkaç farklı ölçüt geliştirilmiştir. Harary, {\em $l(G)$ satır endeksini}, işaretli bir çizge $G$'nin dengeli bir çizgeye dönüşmesi için işaretlerinin değişmesi gereken en küçük kenar sayısı olarak tanımladı. $l(G)$ satır endeksi, dikkate alınması gereken makul bir ölçüt gibi gözükse de, Barahona, işaretli bir çizgenin satır endeksini belirleme sorununun NP-Tam sınıfına dahil problem olduğunu gösterdi. Bu ise nispeten küçük ağlar için bile $l(G)$ değerinin hesaplanabilmesinin nerdeyse imkansız olduğunu göstermektedir. Aslında, tüm kenarların negatif olduğu ağlar için bile, $l(G)$'yi hesaplamak hala NP-Tam zorluktadır. Bu durum zor değildir, çünkü Yapı Teoremine göre en fazla negatif kenarın işaretinin korunması için çizge içindeki en büyük kesit tespit edilmelidir ve bu da çok iyi bilinen NP-Tam sınıfında bir sorudur. Harary tarafından işaretli bir çizgenin dengesizlik miktarını ölçmek için geliştirilen diğer bir ölçüt ise, pozitif döngü sayısının o işaretli çizgedeki toplam döngü sayısına oranıdır. Bu metrikle çalışan Antal ve diğerleri, çizgelerin içlerindeki üçgenlere odaklanan ve işaretli çizgeleri dengelemeye çalışan iki açgözlü (greedy) algoritma geliştirdi. Algoritmaları, toplam negatif üçgenlerin sayısını azalttığı sürece bir kenarın işaretini değiştirmektedir. Antal ve diğerleri ve Strogatz ve diğerleri bu algoritmaların her ikisinin de bazı ağları dengeleyemeyebileceğini göstermiştir, çünkü algoritmalar ağdaki dengesizlik miktarını değerlendirmek için kullanılan enerji fonksiyonlarının yerel ancak küresel olmayan minimumlarında sıkışıp kalabilir. Bu algoritmaların dengeyi sağladığı işaretli çizgeler sınıfı için bile, kenar işaretlerinin değişimindeki rastgelelik yüzünden, algoritmaların gerçek dünya ağları hakkındaki tahmin gücü sorgulanabilir. Yukarıda belirtilen yaklaşımlarda karşılaşılan zorlukların bir sonucu olarak, gerçek sosyal ağlar üzerindeki tahmin gücü göz önüne alınmadan işaretli çizgeleri dengelemeye çalışan yeni algoritmalar geliştirilmiştir. Marvel ve diğerleri hemen hemen tüm işaretli çizgeleri dengeleyen sürekli bir model üzerine inşa edilmiş dinamik bir algoritma geliştirdi. İşaretli bir çizgedeki positif kenar sayısı negatif kenar sayısından fazla ise, algoritmaları her negatif kenarın işaretini positif yaparak dengeli bir çizge oluşturmaktadır. Öte yandan, kenarların çoğunluğu negatif işarete sahipse, algoritmaları iki parçasının büyüklüğü eşit olan dengelenmiş işaretli bir çizge oluşturmaktadır. Bu tezde bu sonuçların sosyal ağların evrimi ile ilgili makul olmayan bir tahmin olduğunu gösteriyoruz. Ayrıca algoritmaları tarafından işareti değiştirilen kenar sayısını $ l(G)$ cinsinden nicelememektedirler. Marvel ve diğerlerinin bu algoritmaları, sosyal ağları sürekli modeller kullanarak dengelemeye çalışan birçok yeni araştırma makalesinin ilham kaynağı olmuştur. Her ne kadar ağları dengeleyebilme açısından Marvel ve diğerlerinin araştırmaları büyük bir başarıysa da, böyle bir algoritmanın gerçek sosyal ağların dönüşümüyle uyuşmadığını göstereceğiz. Bu tezde, ilk önce düğüm kümesinin herhangi bir ikiye parçalanması $(S, \overline S)$ için {\em iyi kenar} ve {\em kötü kenar} kavramları tanımlanmaktadır. İyi kenarlar kümesi, her bir parçanın içinde bulunan pozitif kenarlardan ve uçları farklı parçalarda bulunan negatif kenarlardan oluşur. Kalan kenarlar ise kötü kenarlardır. {\em Bir düğümün kararlılık derecesi} bu düğümün uç noktası olduğu iyi ve kötü kenarların sayısı arasındaki farktır. {\em Bir ikiye parçalanmanın kararlılık derecesi } ise, bu parçalanma için bütün düğümlerin kararlılık derecelerinin toplamıdır. Daha sonra geliştirilen bu yeni ölçütlerin çizgi endeksi ölçütü ile eşdeğer olduğu gösterilmiştir. Karalılık derecesi çizgi endeksine eşdeğer olmasına rağmen, kararlılık derecesi yerel bir ölçüt olması ve bu ölçütü optimize eden algoritmaların geliştirilmesine olanak sağlaması sebebiyle çizge endeksinden üstündür. Tezimizde En Büyük Kesit Algoritması genelleştirilerek oluşturulan böyle bir yerel algoritmayı incelemekteyiz. Algoritmamız başlangıçta $(V(G), \emptyset)$ ikiye parçalanmasından başlıyarak en negatif kararlılık derecesine sahip olan bir düğümü, negatif kararlık derecesine sahip bir düğüm bulunduğu sürece, haraket ettirerek bulunduğu parçayı değiştirir ve basit bazı değişikliklerden sonra sonuç olarak yine farklı bir ikiye parçalanma verir. Bu sonuç parçalanmasındaki bütün kötü kenarların işaretleri değiştirilerek dengeli bir ağ ortaya konur. Algoritmanın polinom zamanda çalışan bir algoritma olduğunu ve tam çizgelerde algoritmanın işaretini değiştirdiği kenar sayısının, tüm kenarları negatif olan tam çizgenin çizgi endeksiyle sınırlı olduğunu ispatlıyoruz. Ayrıca yeni oluşan her parçalanmanın kararlılık derecesinin ve bu parçalanma için her düğümün kararlılık derecesinin, taşınan düğümün kararlılık derecesi cinsinden nasıl değiştiğini hesaplıyoruz. Fakat beklendiği üzere, algoritmanın her zaman $l(G)$ değerine sahip bir parçalanmayı bulamadığını da gösteriyoruz. Bu sonuç, değerlendirilen işaretli çizgeler kümesi tam işaretli çizgeler kümesi ile sınırlandığında bile geçerlidir. Algoritmamızın $l(G)$ değerine sahip bir parçalanmayı her zaman veremediğini, sonsuz bir aile de dahil olmak üzere, bazı tam işaretli çizgeleri örnek vererek gösteriyoruz. Tam işaretli çizgelerin çizge endeksinin hesaplanması probleminin NP-Tam zorlukta olup olmadığı hala açık bir sorudur. Algoritmayı kullanarak, her bir düğümünün en az kötü kenarlar kadar iyi kenarların uç noktası olduğu çizgelerin, çizgi endekslerini hesaplamanın hala NP-Tam olduğunu kanıtlıyoruz. Buna ek olarak, genel bir işaretli çizgenin çizgi endeksini hesaplama sorusunun, yukarıda belirttiğimiz cinsten bir işaretli çizgenin çizgi endeksini hasaplama sorusuna indirgenebileceğini de gösteriyoruz. Marvel ve diğerlerinin algoritması dikkate alındığında bu nokta çok önemlidir. Algoritmaları, verilen işaretli çizgede pozitif kenar yoğunluğu yarıdan fazla olduğunda her zaman bütün kenarları positif olan dengeli bir işaretli çizge oluşturduğundan ve bu cins işaretli çizgelerin çizgi endeksinin hesaplanması kanıtladığımız gibi NP-Tam zorlukta olduğu için, algoritmaları açıkça işareti değiştirilmesi gereken kenar sayısını optimize etmemektedir. Buna ek olarak, algoritmamızın onların algoritmasından daha az kenarın işaretini değiştirdiği ve positif kenarların yoğunluğunun yarıdan fazla olduğu işaretli çizge örnekleri sunuyoruz. Yapısal denge teorisinin asıl amacı, gerçek sosyal ağların gelişimini öngörmek olduğundan, işaretli çizgeleri dengelemek için geliştirilen herhangi bir algoritmanın başarısı, böyle bir algoritmanın gerçek sosyal ağların gelişimini öngörme becerisine bağlı olacaktır. Bu yüzden algoritmamızı iki basit ağa uyguluyoruz. Mevcut Suriye Savaşı'nın parçası olan beş büyük devletten oluşan sosyal ağ ile 34 kişilik bir Karate Klübünün üyelerinden olan sosyal ağı inceliyoruz. Bu iki ağın yapısına ilişkin veriler iki akademik makaleden elde edilmiştir. Algoritmamız bu ağların son halini büyük bir isabet oranıyla tahmin etmiştir. Daha büyük sosyal ağlar hakkında veri eksikliği nedeniyle algoritmamızı daha büyük ağlara uygulayamadık. Daha geniş ağları inceleyen sınırlı sayıda akademik makale mevcuttur ve bu makalelerde büyük sosyal ağlar için Heider'in denge teorisinin varsayımlarının fazlaca basit olabileceği sonucuna varılmıştır. Heider'in araştırmalarına sıklıkla yapılan iki eleştiri, ilişkilerin simetrik olduğu varsayımının ve ilişkilerin herhangi bir ağırlığının olmadığı varsayımının gerçekçi olmadığıdır. Algoritmamız kolaylıkla ağırlıklı çizgeler üzerinde çalışacak şekilde değiştirilebileceğinden yukarıdaki ikinci eleştiri yaptığımız çalışma için geçerli değildir. İlk noktaya cevap vermek için, algoritmamızı yönlü ve ağırlıklı çizgeler üzerinde çalışacak şekilde geliştirmeyi ve eğer veriler bulunabilirse bu tür bir algoritmayı daha büyük sosyal ağlara uygulamayı umuyoruz.

Özet (Çeviri)

In this thesis, we study the optimization of complete signed graphs. We develop a graph theoretical algorithm that balances any signed graph with specific attention paid to complete signed graphs. In 1946, Heider observed that the relationships between members of some social networks do not change easily, while relationships in other networks do. He observed that among all networks consisting of three people, the relationships are stable when all members are friendly towards each other or if two friends are mutually hostile towards a third member. He characterized these networks as balanced triads and the remaining networks consisting of three people as unbalanced triads. He postulated that larger networks will be balanced when every triad of such a network is balanced. Later research in the field of structural balance has been concentrated on three main issues: Determining whether or not a given social network is balanced, developing reasonable metrics that quantify how balanced a given social network is, and developing algorithms that balance any social network and examining their correspondence to the transformations of real world social networks. Cartwright and Harary showed that Heider's observations can be summarized using signed graphs. They defined a {\em balanced signed graph} as a graph where the product of edge signs of every cycle of $G$ is positive. However, this condition is computationally difficult to check in a general signed graph. To overcome this difficulty Cartwright and Harary proved the Structure Theorem which states that, a signed graph $G$ is balanced if its vertex set can be partitioned into two disjoint sets (one of which could possibly be empty) such that edges lying inside each of the sets are positive edges, while edges with endpoints in different sets are negative. This condition is much easier to verify than the cycle condition since by the Structure Theorem the set of negative edges has to form a bipartite graph, which is a computationally simple condition to check. If the graph of negative edges is bipartite, we can immediately identify the two parts during this process. What remains is answering whether there are any positive edges between the two parts, if not the network is balanced. To measure the amount of imbalance in a signed graph several metrics have been developed. Harary defined the {\em line index, $l(G)$} of a signed graph $G$ as the minimum number of edges whose signs need to be negated so that the resultant signed graph is balanced. The line index $l(G)$ seems like a reasonable metric to consider, however, Barahona showed that the problem of determining the line index of a signed graph is an NP-Complete problem, meaning that most probably it is computationally infeasible even for relatively small networks. In fact even for networks in which all edges are negative, computing $l(G)$ is still of NP-Complete complexity. This case is not difficult, since by the Structure Theorem, to preserve the largest number of the original negative edges, one needs to identify the largest bipartite subgraph of the original network. This is the well known NP- Complete problem of finding a MAX-CUT of a given graph. Another metric introduced by Harary to measure the amount of imbalance of a signed graph is the ratio of the number of positive cycles to the total number of cycles in that signed graph. Working with this metric, Antal et al. developed two greedy algorithms for balancing complete signed graphs focusing on triangles. Their algorithm negates the sign of an edge as long as the negation reduces the total number of negative triangles. Their algorithms cannot balance all signed graphs. Antal et al. and Strogatz et al. have shown that both of these algorithms may not balance some networks because the algorithms may get stuck in ''jammed states'', which are local but not global minima of the energy functions used to evaluate the amount of imbalance in a network. It may be said that even for the class of signed graphs, where these algorithms achieve balance, due to the randomness involved in negating edges, the predictive power of these algorithms about real world networks could be questionable. As a consequence of the perceived difficulties of the approaches mentioned above, new algorithms have been developed which only try to balance signed graphs without much consideration of their predictive power. Marvel et al. developed a dynamic algorithm using a continuous model that balances almost all graphs. They demonstrated that if there are more positive edges than negative edges in the signed graph their algorithm produces a complete signed network by negating the sign of every negative edge. On the other hand, if the majority of the edges have negative sign, their algorithm outputs a balanced signed graph by partitioning the vertex set in to two parts of equal size. We show this is an unreasonable prediction about the evolution of social networks. They also do not quantify the number of edges negated by their algorithm in terms of $l(G)$. The approach in Marvel et al. has been the inspiration of many new research articles that try to balance social networks using continuous models. Although from the perspective of being able to balance networks the work of Marvel et al. is a major achievement, we will show that such an algorithm may fail to correspond with the transformations of actual social networks. In this thesis we first define {\em good edges} and {\em bad edges} for a given bipartition of the vertex set of a signed graph. The set of good edges is composed of positive edges that lie inside each part and negative edges that have each endpoint in a different part. The remaining edges are bad edges. We then develop a new metric, {\em the stability degree of a vertex}, which is the difference between the number of good edges and bad edges incident to that vertex for a given partition of the vertex set. We define {\em the stability degree of a partition $(S, \overline S)$} as the sum of the stability degree of each vertex of the signed graph for the partition $(S, \overline S)$. We proceed to show that the stability degree of a partition and the line index of a partition are equivalent as parameters, with stability degree having the advantage that it is a local parameter to which local maximization algorithms can be applied. We consider one such algorithm based on the greedy Max- Cut algorithm. Our algorithm initializes with the partition $(V(G), \emptyset)$ and moves a vertex with the least stability degree as long as a vertex with negative stability degree exists and terminates after minor modifications when such a vertex does not exist. We then switch the signs of every bad edge of the final partition to yield a balanced signed graph. We prove that the algorithm is a polynomial time algorithm and that, the number of edges of a complete signed graph whose signs are flipped, is bounded by the line index of the complete signed graph of all negative edges. We also calculate how the stability degree of each vertex and the stability degree of each new partition changes in terms of the stability degree of the vertex which was moved. We show as expected that the algorithm does not always output a partition which achieves $l(G)$. This conclusion holds even when the set of signed graphs is restricted to complete signed graphs. We provide several examples of complete signed graphs, including an infinite family, where our algorithm fails to output a partition which achieves $l(G)$. It is still an open question whether computing the line indices of complete signed graphs is of NP- Complete difficulty. Using the algorithm we prove that computing the line indices of graphs, where each vertex is the endpoint of at least as many good edges as bad edges, is still NP-Complete. We in fact reduce the problem of computing the line index of any signed graph to computing the line index of a signed graph of the type mentioned above. This point is crucial when considering the algorithm of Marvel et. al. Because their algorithm always yields a balanced signed graph with all positive edges when the input signed graph has a higher density of positive edges, and computing the line index of such signed graphs is NP-Complete as we have proved, their algorithm clearly does not optimize the number of edges whose signs have to be flipped. Indeed we provide examples of signed graphs where the density of positive edges is greater where our algorithm forces much fewer changes on the edge signs of the underlying signed graph. Since the original goal of structural balance theory was to predict the evolution of actual social networks, the success of any algorithm developed to balance signed graphs will depend on whether or not such an algorithm predicts the evolution of real social networks. As such we have applied our algorithm to two simple networks. We considered the network formed by the five major state participants in the current Syrian War and a social network of members of a 34 person Karate Club. Data on the structure of these two networks was recorded in two academic papers. Our algorithm predicted the final state of these networks with great accuracy. Lacking data on larger social networks, we have not been able to apply our algorithm to larger networks. There have been a limited number of research articles considering larger networks which make the conclusion that Heider's balance theory may be too simplistic when considering large social networks. Two criticisms made of Heider's research have been that the assumptions that relationships are symmetric and that they lack magnitude are not realistic. The second criticism does not hold for our algorithm since it can be modified slightly to work on weighted graphs. To answer the first point we hope to develop our algorithm in future research to work on directed weighted graphs and apply any such algorithm to real social networks if data is available.

Benzer Tezler

  1. Tez No

    819889

    Türkiye'nin dijital diplomasisi: Rusya'nın Ukrayna işgalinde Türkiye'nin tahıl koridoru diplomasisi

    Türkiye's digital diplomacy: Türkiye's grain corridor diplomacy amid Russia's invasion of Ukraine

    BENGİNUR İKBAL AKGÜL

    Yüksek Lisans

    Türkçe

    Türkçe

    2023

    Uluslararası İlişkilerİstanbul Medeniyet Üniversitesi

    Uluslararası İlişkiler Ana Bilim Dalı

    PROF. DR. İSMAİL ERMAĞAN

  2. Tez No

    403423

    Decentralized graph processes for robust multi-agent networks

    Başlık çevirisi yok

    AHMET YASİN YAZICIOĞLU

    Doktora

    İngilizce

    İngilizce

    2014

    Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve KontrolGeorgia Institute of Technology

    Dr. JEFF S. SHAMMA

    Dr. MAGNUS EGERSTEDT

  3. Tez No

    670279

    German-Turkish women's transnational practices and belonging at intersecting social divisions

    Alman-Türk kadınların toplumsal bölmelerindeki çok uluslu işleri ve aidiyet

    MELANIE WEIßENBERG

    Doktora

    İngilizce

    İngilizce

    2021

    Sosyolojiİstanbul Bilgi Üniversitesi

    Siyaset Bilimi Bilim Dalı

    PROF. DR. AYHAN KAYA

  4. Tez No

    880514

    2023 Maraş Depreminde görev alan sağlık çalışanlarının travma sonrası stres ve psikolojik dayanıklılık açısından değerlendirilmesi: Kırıkkale ili örneği

    Evaluation of health workers who worked in the 2023 Maraş Earthquake in terms of post-traumatic stress and psychological resistance: The case of Kırıkkale province

    ADİL ASLAN

    Yüksek Lisans

    Türkçe

    Türkçe

    2024

    Sağlık YönetimiKırıkkale Üniversitesi

    Sağlık Yönetimi Ana Bilim Dalı

    DOÇ. DR. ÖZGÜR SELVİ

  5. Tez No

    880311

    Improving the performance of 1D vertex parallel GNN training on distributed memory systems

    Dağıtık bellek sistemlerinde 1D düğüm paralel GNN eğitiminin performansının iyileştirilmesi

    KUTAY TAŞCI

    Yüksek Lisans

    İngilizce

    İngilizce

    2024

    Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrolİhsan Doğramacı Bilkent Üniversitesi

    Bilgisayar Mühendisliği Ana Bilim Dalı

    PROF. DR. CEVDET AYKANAT

Geri Dön