Multiplicity in the Partitioning of Signed Graphs
İşaretli Grafların Kümeleme Analizinde Çoklu Topluluk Yapısı Kavramı
- Tez No: 936842
- Danışmanlar: DOÇ. DR. VİNCENT LABATUT
- Tez Türü: Doktora
- Konular: Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrol, Computer Engineering and Computer Science and Control
- Anahtar Kelimeler: Belirtilmemiş.
- Yıl: 2021
- Dil: Fransızca
- Üniversite: Dıger
- Enstitü: Yurtdışı Enstitü
- Ana Bilim Dalı: Bilgisayar Mühendisliği Ana Bilim Dalı
- Bilim Dalı: Bilgisayar Bilimleri Bilim Dalı
- Sayfa Sayısı: Belirtilmemiş.
Özet
İşaretli graflar, düğümler arasında pozitif ya da negatif bağlantılar içeren graflardır. Fritz Heider'in Denge Kuramına göre, topluluk/küme yapısı belli olan işaretli bir grafın dengeli kabul edilmesi için, pozitif bağlantıların aynı topluluktaki düğümler arasında ve negatif bağlantıların ise farklı topluluklardaki düğümler arasında bulunması gerekir. Fakat, gerçek hayatta karşımıza çıkan graflar nadiren dengelidir. Yani, nasıl bir topluluk yapısı elde edersek elde edelim, bazı pozitif bağlantılar farklı topluluklardaki düğümler arasında ve/veya bazı negatif bağlantılar aynı topluluktaki düğümler arasında olacaktır. Bu durumda, dengesizliğin büyüklüğünün ölçülmesi ve hangi bağlantıların dengesizliğe sebep olduğunun bilinmesi, graf analizi bakımından önemli bir yer tutar. Korelasyon Kümeleme (KK) problemi (Correlation Clustering), tam olarak minimum dengesizliğe sahip olan topluluk yapısının bulunması olarak tanımlanır. İşaretli graflarda Denge Kuramına göre topluluk yapısı bulma, graf tarafından modellenen sistemi anlamaya yardımcı olması nedeniyle birçok uygulaması olan önemli bir çalışmadır. Bununla birlikte, literatürde kullanılan standart yaklaşım, tek bir topluluk yapısı bulmak ve analizin geri kalanını, incelenen sistemi tam olarak karakterize etmek için yeterliymiş gibi sadece bu topluluk yapısına odaklanmaktır. Oysa bu, grafın iç dinamiğini tamamiyle yansıtmayabilir. Dolayısıyla, graf tarafından modellenen sistemi daha kapsamlı anlamak amacıyla, başka birden fazla topluluk yapılarının bulunması gerekebilir. Her ne kadar bu birden fazla topluluk yapısı arama ihtiyacı son kullanıcının bakış açısından son derece önemli olsa da, şimdiye kadar sadece çok az sayıda çalışma analizlerinde bunu dikkate almıştır. Bu tezde, geleneksel tek topluluk yapısı varsayımını gevşeterek iki ayrı durumda birden fazla topluluk yapısı arıyoruz. Bunlardan ilki, işaretli çok katmanlı graflar bağlamında ortaya çıkmaktadır. Genel olarak çok katmanlı graflarda topluluk yapısı bulmak için önerilen tüm geleneksel yaklaşımlar tek bir topluluk yapısı varsayımına dayanmaktadır. Bu sınırlamanın üstesinden gelmek için, bireysel katmanların topluluk yapısını birleştirmeden önce bir meta-kümeleme sürecini entegre eden ve yapısal olarak benzer katmanların belirlenmesine olanak tanıyan yeni bir topluluk yapısı bulma yöntemi öneriyoruz. Bu yöntemi, bir Avrupa Parlamentosu veri setine uygulayarak, her biri aynı yasa koyucuların farklı karakteristik oy verme modellerine karşılık gelen birden fazla topluluk yapısı elde edebildik. Bu tür kalıpların ortaya çıkışı, yalnızca geleneksel yaklaşımlar göz önünde bulundurulduğunda tamamen gizliydi. Örneğin, sadece Fransız S&D ve ALDE milletvekillerinin alternatif olarak sol ve sağ parti grupların yanında yer aldığını teyit etmekle kalmadık, aynı zamanda bu değişimlerin hangi konularla ilgili olduğunu da belirledik. İkinci durum, KK problemine özgüdür. Bu problemi bir işaretli graf üzerinde çözerken, birkaç veya hatta birçok optimal topluluk yapısı bir arada bulunabilir. Birden fazla optimal topluluk yapısının bir arada bulunması halinde, bunların ne kadar farklı/çeşitli olduğunun bilinmesi, graf tarafından modellenen sistemi anlamaya yardımcı olması sebebiyle önemlidir. Başka bir deyişle, birden fazla topluluk yapısı varken yalnızca bir topluluk yapısını dikkate aldığımızda ne kaybettiğimizi bilmek isteriz. Bu sorulara cevap verebilmek için, ideal olarak optimal topluluk yapı uzayını bulmak, diğer bir deyişle, bütün optimal topluluk yapılarını bulmak, ve bunların analizini yapmak gerekir. Bu doğrultuda, öncelikle optimal topluluk yapı uzayını bulan yeni verimli bir metod sunuyoruz. Daha sonra, bu bulduğumuz uzayı, ampirik olarak incelemek için küme analizi tabanlı yeni bir sistem öneriyoruz. Ampirik çalışmamıza dayanarak, 4 farklı uzay topolojisi elde ettik: 1) yalnız bir topluluk yapısı; 2) yapısal olarak birbirine çok benzeyen topluluk yapılarını barındıran tek bir küme; 3) her küme yapısal olarak birbirine çok benzeyen topluluk yapılarını barındıran birden fazla kümeler (doğal olarak, aynı kümede bulunmayan topluluk yapıları yapısal olarak birbirinden farklıdır); 4) yapısal olarak karmaşık benzerlikte (hem benzer hem farklı) topluluk yapıları barındıran tek bir küme. Son olarak, bu bahsedilen önceki iki durumda da topluluk yapıları arasındaki benzerliğin hesaplanması gerekir. Topluluk yapısı bulma bağlamında, bu görev dış değerlendirme ölçütü olarak adlandırılan bir ölçüt aracılığıyla yapılabilir. Ancak, literatürde her biri farklı özelliklere sahip olan birçok ölçüt mevcuttur. Bu durum, en uygun ölçütü seçme açısından son kullanıcının işini zorlaştırmaktadır. Bu amaçla, son kullanıcıların kolayca yorumlayabileceği sonuçlar üretmek için yeni bir ampirik değerlendirme sistemi öneriyoruz. Literatürde popüler ölçütlerden oluşan bir koleksiyon için, ilk olarak, önceden tanımlanmış bir dizi parametre ve transformasyon aracılığıyla topluluk yapıları üretiyoruz. İkinci olarak, değerlendirme sistemimiz, bu parametrelerden ve transformasyonlardan nasıl etkilendikleri açısından ölçütleri karakterize etmektedir. Sonuçlarımız, sistemimizin her bir ölçütün sahip olduğu arzu edilen özellikleri tanımlamaya izin verdiğini göstermektedir. Bazıları için sonuçlarımız, literatürde halihazırda yayınlanmış olan ampirik ve teorik bulguları doğrulamaktadır. Diğerleri için ise, yaklaşımımızın sistematik yapısı literatürde daha önce bahsedilmeyen özellikleri bile ortaya çıkarmaktadır.
Özet (Çeviri)
According to the structural balance theory, a signed graph is considered structurally balanced when it can be partitioned into a number of modules such that positive edges are located inside the modules and negatives ones are in-between them. In practice, real-world networks are rarely perfectly balanced. When it is not the case, one wants to measure the magnitude of the imbalance and to identify the set of edges related to the network imbalance. The Correlation Clustering (CC) problem is precisely defined as finding the partition with minimal imbalance. Signed graph partitioning is an important task, which has many applications, as finding a balanced partition helps understanding the system modeled by the graph. However, the standard approach used in the literature is to find a single partition and focus the rest of the analysis on it, as if it was sufficient to fully characterize the studied system. Yet, it may not reflect the meso-structure of the network, and one may need to seek for other partitions to build a better picture. Although this need to look for multiplicity is extremely important from the end user's perspective, only a very few works took it into consideration in their analysis, up to now. In this thesis, we want to relax this traditional single-partition assumption to allow searching for multiple partitions in two separate situations. The first one arises in the context of signed multiplex networks. All traditional approaches proposed to partition multiplex networks in general are based on the single-partition assumption. To overcome this limitation, we propose a new partitioning method that integrates a meta-clustering process before merging the partitions of individual layers, which allows identifying structurally similar layers. By applying it to a European Parliament dataset, we could obtain multiple partitions, each corresponding to a different characteristic voting pattern of the same considered legislators. The emergence of such patterns was completely hidden when considering only traditional approaches. For instance, we could not only confirm that the French S&D and ALDE MEPs alternatively side with the left- and right-wing groups, but also identified which topics are concerned by these swings. The second situation is specific to the CC problem. When solving an instance of such problem, several or even many optimal partitions may coexist. If multiple optimal partitions coexist, one can then wonder how different/diverse they are. Put differently, we want to know what we loose when considering only one partition, while there might be multiple ones. In order to answer these questions, one should ideally enumerate completely the space of optimal partitions, and perform its analysis. To this end, we propose a new efficient solution space enumeration method and a cluster analysis-based framework in order to first enumerate the space of optimal partitions and then empirically study such space. Based on our empirical study, our main finding is the identification of 4 different situations: 1) unique solution; 2) single class of similar solutions; 3) several classes of similar solutions; 4) multiple solutions without a clear clustering structure. Lastly, each of these previous situations requires to compute the similarity between partitions. In the context of graph partitioning, this task can be done through a so-called external evaluation measure. However, there exist many such measures, each having different characteristics. This makes it challenging to select the most appropriate for a given situation for the end user. To this end, we propose a new empirical evaluation framework in order to produce results that end users can easily interpret. For a collection of candidate measures, it first consists in describing their behavior by computing them for a generated dataset of parametric partitions, obtained by applying a set of predefined parametric partition transformations. Second, our framework characterizes the measures in terms of how they are affected by these parameters and transformations. Our results show that our framework allows identifying the desirable properties possessed by each measure. For some of them, our results confirm empirical and theoretical findings already published in the literature. For others, the systematic nature of our approach even uncovers properties not mentioned before in the literature.
Benzer Tezler
- Many‐objective multi‐criteria diet optimization problem
Çok amaçlı çok kriterli diyet eniyileme problemi
CUMALİ TÜRKMENOĞLU
Doktora
İngilizce
2023
Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrolİstanbul Teknik ÜniversitesiBilgisayar Mühendisliği Ana Bilim Dalı
PROF. DR. AYŞE ŞİMA ETANER UYAR
DR. ÖĞR. ÜYESİ BERNA KİRAZ
- Sahada programlanabilir kapı dizileri ile lojik devre tasarımı ve VHDL kullanılarak bazı devrelerin gerçekleştirilmesi
Başlık çevirisi yok
ATEŞ BERNA
Yüksek Lisans
Türkçe
1998
Elektrik ve Elektronik Mühendisliğiİstanbul Teknik ÜniversitesiElektronik ve Haberleşme Mühendisliği Ana Bilim Dalı
PROF. DR. AHMET DERVİŞOĞLU
- Inconsistency and multiplicity in the self
Benlikte görülen tutarsızlık ve çoğulluk
MEHMET ABDULKERİM TETİK
Yüksek Lisans
İngilizce
2019
PsikolojiBoğaziçi ÜniversitesiBilişsel Bilimler Ana Bilim Dalı (disiplinlerarası)
PROF. DR. STEPHEN VOSS
- Kıpçak grubu Türk lehçelerinde çokluk ve birliktelik bildiren ifadeler
Expressions indicating multiplicity and unity in the Kypchaq group of Turkic dialects
ALEYNA ALEVSAÇAN
Yüksek Lisans
Türkçe
2025
DilbilimFırat ÜniversitesiÇağdaş Türk Lehçeleri ve Edebiyatları Ana Bilim Dalı
PROF. DR. SÜLEYMAN KAAN YALÇIN