Characterizing and detecting cohesive subgroups with applications tosocial and brain network
Yogun ve uyumlu alt grupları karakterize etme ve tespit etme, sosyal media ağları ve beyin ağlari
- Tez No: 782215
- Danışmanlar: PROF. DR. SERGİY BUTENKO
- Tez Türü: Doktora
- Konular: Endüstri ve Endüstri Mühendisliği, Industrial and Industrial Engineering
- Anahtar Kelimeler: Belirtilmemiş.
- Yıl: 2015
- Dil: İngilizce
- Üniversite: Texas A&M University
- Enstitü: Yurtdışı Enstitü
- Ana Bilim Dalı: Endüstri Mühendisliği Ana Bilim Dalı
- Bilim Dalı: Belirtilmemiş.
- Sayfa Sayısı: 116
Özet
Birçok karmaşık sistem, birbirleriyle çeşitli ilişkiler yoluyla etkileşime giren varlıkları içerir (örneğin, sosyal sistemlerdeki insanlar, beyindeki nöronlar). Bu varlıklar ve etkileşimler, çeşitli avantajlar nedeniyle genellikle grafikler kullanılarak temsil edilir. Bu tez, grafik teorisi ve optimizasyonunda yeni yöntemler için teori ve algoritmalar geliştirmeye ve bunların sosyal ağlara ve beyin ağlarına uygulamalarına odaklanmaktadır. Spesifik olarak, bu tezin başlıca katkıları üç yönlüdür. İlk olarak, bu tez, yalnızca yapısal bir metrik olan kümeleme katsayısına dayalı yeni bir klik gevşetme modeli geliştirmeyi değil, aynı zamanda bu modeli kullanarak yeni bir grafik kümeleme algoritması getirmeyi amaçlamaktadır. Klik gevşemeleri, sosyal ağ analizinde uyumlu alt grupların klasik modellerinde kullanılır. Kümeleme katsayısı, son zamanlarda küçük dünya ağlarını karakterize eden yapısal bir özellik olarak tanıtıldı. Uyumlu alt gruplar ve küçük dünya ağları (yani, küçük yol uzunluklarıyla yüksek oranda kümelenmiş grafikler) kavramları arasındaki benzerliklerden yararlanılması. Bu tezin ilk kısmı, karşılık gelen uyarılmış alt grafikte kümeleme katsayısı üzerinde bir alt sınır α uygulayarak tanımlanan yeni bir klik gevşemesi olan α-kümesini tanıtmaktadır. Kümelenme katsayısının yerel ve küresel kümelenme katsayısı olmak üzere iki farklı tanımı ele alınmaktadır. α-kümelerinin belirli yapısal özellikleri analiz edildi ve bir ağdaki en büyük α-küme boyutunu belirlemek için matematiksel optimizasyon modelleri geliştirildi ve birkaç gerçek hayattaki sosyal ağ örneğine uygulandı. Ek olarak, yerel α-kümesine dayalı bir ağ kümeleme algoritması tanıtılmış ve başarılı bir şekilde değerlendirilmiştir. İkincisi, bu tez, α-kümelerinin özel bir durumu olarak ortaya çıkan, kliklerin maksimum bağımsız birliği sorunu (maksimum IUC sorunu) adı verilen yeni bir matematiksel modeli araştırıyor. Hem maksimum klik hem de maksimum bağımsız kümelerin uygulanabilir çözümler olduğu ve bunların tek tek karşılık gelen boyutlarının, IUC çözümünün boyutu için alt sınırlar olduğu ilginç bir problemdir. Farklı grafik türlerinin (düzlemsel, birim disk grafikler ve pençesiz grafikler) yapısal özelliklerinin yanı sıra karmaşıklık sonuçları sunulduktan sonra, bir tamsayı programlama formülasyonu geliştirildi, ardından bir dal-sınır algoritması ve birkaç klikler probleminin maksimum bağımsız birliğine yaklaşmak için buluşsal yöntemler.Geliştirilen yöntemler birçok kıyaslama örneği üzerinde ampirik olarak değerlendirilmiştir. Son olarak, Teksas Preklinik Çalışmalar Enstitüsü (TIPS) ile işbirliği içinde olan bu tez, beyin sarsıntısının hayvan beyinleri üzerindeki etkisini anlamak için yeni bir deneysel veri keşfetmek üzere klik gevşeme modellerini uyguluyor. Araştırmamız, benzersiz ve yeni bir deneysel veri kullanan hayvan beyni ağlarının uyumlu ve sağlam kümeleme analizini içerir. TIPS ile işbirliği içinde, beyin sarsıntısından önce ve sonra ölçülen hayvan beyinleri hakkında çok sayıda fMRI verisi çiftini analiz ettik. Önce hayvan beyinlerindeki benzer bölgeleri belirlemek için ağ analizinden yararlanıyoruz ve ardından bu bölgelerin yanı sıra grafik yapısal özelliklerin bir sarsıntıdan önce ve sonra nasıl değiştiğini karşılaştırıyoruz. Bildiğimiz kadarıyla, bu çalışma sadece beyin sarsıntısı seviyesi ile işlevsel birim etkileşimi arasındaki ilişkiyi açık bir şekilde incelemesiyle değil, aynı zamanda beyin verilerinin çok ayrıntılı ve ince taneli fMRI ölçümlerini kullanmasıyla literatürde benzersizdir.
Özet (Çeviri)
Many complex systems involve entities that interact with each other through var- ious relationships (e.g., people in social systems, neurons in the brain). These entities and interactions are commonly represented using graphs due to several advantages. This dissertation focuses on developing theory and algorithms for novel methods in graph theory and optimization, and their applications to social and brain networks. Specifically, the major contributions of this dissertation are three fold. First, this dissertation aims not only to develop a new clique relaxation model based on a structural metric, clustering coefficient, but also to introduce a novel graph clustering algorithm using this model. Clique relaxations are used in classical models of cohesive subgroups in social network analysis. Clustering coefficient was introduced more recently as a structural feature characterizing small-world networks. Leveraging the similarities between the concepts of cohesive subgroups and small-world networks (i.e., graphs that are highly clustered with small path lengths). The first part of this dissertation introduces a new clique relaxation, α-cluster, defined by enforcing a lower bound α on the clustering coefficient in the corresponding induced subgraph. Two different definitions of the clustering coefficient are considered, namely, the local and global clustering coefficient. Certain structural properties of α-clusters are analyzed, and mathematical optimization models for determining the largest size α-clusters in a network are developed and applied to several real-life social network instances. In addition, a network clustering algorithm based on local α-cluster is introduced and successfully evaluated. Second, this dissertation explores a novel mathematical model called the max- imum independent union of cliques problem (max IUC problem), which arises as a special case of α-clusters. It is an interesting problem for which both the maximum clique and maximum independent sets are feasible solutions and individually their corresponding sizes are lower bounds for the size of the IUC solution. After present- ing the structural properties as well as the complexity results of different graph types (planar, unit disk graphs and claw-free graphs), an integer programming formula- tion is developed, followed by a branch-and-bound algorithm and several heuristic methods to approximate the maximum independent union of cliques problem.The developed methods have been empirically evaluated on many benchmark instances. Finally, this dissertation, in collaboration with Texas Institute of Preclinical Stud- ies (TIPS), applies clique relaxation models to explore a new experimental data to understand the effect of concussion on animal brains. Our research involves cohesive and robust clustering analysis of animal brain networks utilizing a unique and novel experimental data. In collaboration with TIPS, we have analyzed multiple pairs of fMRI data about animal brains that are measured before and after a concussion. We utilize network analysis to first identify the similar regions in animal brains, and then compare how these regions as well as graph structural properties change before and after a concussion. To the best of our knowledge, this study is unique in the literature in that it not only explicitly examines the relation between concussion level and the functional unit interaction but also uses very detailed and fine-grained fMRI measurements of brain data.
Benzer Tezler
- Antenna and measurement system for microwave imaging of breast tumors
Meme tümörünün mikrodalga ile görüntülenebilmesi için anten ve ölçüm sistemi
MEHMET ABBAK
Doktora
İngilizce
2015
Mühendislik Bilimleriİstanbul Teknik Üniversitesiİletişim Sistemleri Ana Bilim Dalı
PROF. DR. İBRAHİM AKDUMAN
- Detecting and characterizing anomalous followers on social media
Sosyal medyada anormal takipçileri tespit etme ve karakterize etme
BARIŞ TEMEL
Yüksek Lisans
İngilizce
2022
Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve KontrolSabancı ÜniversitesiVeri Bilimi Ana Bilim Dalı
YRD. DOÇ. DR. ONUR VAROL
- Diyarbakır ve civarında karpuz üretim alanlarında karpuz mozaik virüs (Watermelon mosaic potyvirus, WMV)' ünün saptanması, biyolojik ve moleküler karakterizasyonu
Detection of watermelon mosaic virus (Watermelon mosaic potyvirus, WMV), biological and molecular characterization in Diyarbakir and its surroundings
DİLAN KONUR
Yüksek Lisans
Türkçe
2021
ZiraatÇukurova ÜniversitesiBitki Koruma Ana Bilim Dalı
PROF. DR. SAADETTİN BALOĞLU
- Land cover change assessment in the belek forestland with multidate satellite imagery using change vector analysis technique
Çok zamanlı uydu görüntüleri ile belek ormanlık alanlarındaki arazi örtüsü değişiminin vektör değişim analizi yöntemi ile değerlendirilmesi
AYDA FITRIYE AKKARTAL
Yüksek Lisans
İngilizce
2008
Jeodezi ve Fotogrametriİstanbul Teknik ÜniversitesiUydu Haberleşmesi ve Uzaktan Algılama Ana Bilim Dalı
PROF. DR. AYŞE FİLİZ SUNAR