Sampling methods for random simple and bipartite graphs with prescribed degree sequences
Derece dizili rastgele basit ve iki parçalı çizgeler için örnekleme yöntemleri
- Tez No: 497905
- Danışmanlar: DOÇ. DR. ALİ TAYLAN CEMGİL
- Tez Türü: Yüksek Lisans
- Konular: Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrol, Matematik, Computer Engineering and Computer Science and Control, Mathematics
- Anahtar Kelimeler: Belirtilmemiş.
- Yıl: 2017
- Dil: İngilizce
- Üniversite: Boğaziçi Üniversitesi
- Enstitü: Fen Bilimleri Enstitüsü
- Ana Bilim Dalı: Bilgisayar Mühendisliği Ana Bilim Dalı
- Bilim Dalı: Bilgisayar Mühendisliği Bilim Dalı
- Sayfa Sayısı: 71
Özet
Karmaşık ağlar son yıllarda biyolojik ve sosyal ağlar gibi çizgelerle modellenen gerçek sistemlerdeki çalışmaların artmasıyla oldukça dikkat çekti. Bu alandaki bir problem de derece dizileri veya kümelenme katsayısı gibi belirli özellikleri sağlayan çizge topluluğundan tipik örneklerin üretilmesidir. Bu tezde, basit ve iki parçalı çizgeler için örnekleme problemi ele alınmıştır. Kenar geçiş adımlarına dayanan doğal bir Markov zinciri yöntemi basit çizgeler için sunulmuştur. Belirli bir derece dizisinin olası gerçekleşimleri üzerine doğrudan tekdüze dağılımdan örneklerin elde edilmesinin zorluklarından dolayı, basit ve iki parçalı çizgeler için önem örnekleme ve sıralı öonem örnekleme tekniklerini kullanan algoritmalar araştırılmıştır. Burada, Blitzstein ve Diaconis ve Chen ve ark. tarafından sunulan algoritmalar üzerinde duruyoruz. İki parçalı çizgeler için Miller ve Harrison tarafından önerilen bir yöntemi basit çizgeler için adapte ederek ve dönüştürerek yeni bir tekdüze örnekleme ve tam sayma algoritması önerilmiştir. Son olarak algoritmaların uygulamaları hipotez testi, ağ analizi ve grafik sayımı gibi çeşitli örneklerde gösterilmiştir.
Özet (Çeviri)
Complex networks have attracted considerable attention in recent years with the increase in the studies of real systems modeled by graphs such as biological and social networks. One problem in this domain is the generation of typical instances from a collection of graphs admitting certain properties, such as the degree sequence or the clustering coefficient. In this thesis, the sampling problem is addressed for simple and bipartite graphs with a given fixed degree sequence. A natural Markov chain method relying on the edge switching steps is introduced for simple graphs. Due to the difficulties of directly obtaining samples from the uniform distribution over the set of possible realizations of a given degree sequence, algorithms using importance sampling and sequential importance sampling techniques are investigated for simple and bipartite graphs. Here, we focus on algorithms proposed by Blitzstein and Diaconis and Chen et al. A new uniform sampling and exact counting algorithm is proposed for simple graphs by adapting, and transforming the method suggested by Miller and Harrison for bipartite graphs. Lastly, applications of the algorithms are illustrated in several examples such as hypothesis testing, network analysis and graph enumeration.
Benzer Tezler
- Comparison of established sampling methods for annual Industry and service statistics survey by TURKSTAT
TÜİK yıllık iş istatistikleri sanayi ve hizmet araştırması verileri için oluşturulan örnekleme yöntemlerinin karşılaştırılması
SİBEL ŞAHİN YAŞA
Yüksek Lisans
İngilizce
2018
İstatistikDokuz Eylül Üniversitesiİstatistik Ana Bilim Dalı
DOÇ. DR. SÜLEYMAN ALPAYKUT
- Advanced statistical methods for intelligent transportation systems
Akıllı ulaşım sistemleri için ileri istatistiksel yöntemler
BÜŞRA GÜNGÖR
Doktora
İngilizce
2022
İstatistikDokuz Eylül Üniversitesiİstatistik Ana Bilim Dalı
PROF. DR. SELMA GÜRLER
- Çeşitli sıralı küme örneklemesi yöntemleri ve uygulama
Various ranked set sampling methods and application
YEŞİM ÜNYAZICI
Yüksek Lisans
Türkçe
2002
İstatistikHacettepe Üniversitesiİstatistik Ana Bilim Dalı
PROF. DR. HÜLYA ÇINGI
- Sağlık bilimlerinde örnekleme yöntemleri konusunda karşılaştırmalı ve uygulamalı bir çalışma
An applied and comparative study of sampling methods in medical sciences
YUSUF KARADEMİR
Yüksek Lisans
Türkçe
1999
Tıbbi Biyolojiİstanbul ÜniversitesiBiyoistatistik ve Demografi Ana Bilim Dalı
PROF.DR. YAKUT IRMAK ÖZDEN
- Jackknife ve bootstrap yöntemlerine ilişkin bir uygulama
An application on the jackknife and bootstrap method
ELİF BİÇER
Yüksek Lisans
Türkçe
2022
İstatistikBitlis Eren Üniversitesiİstatistik Ana Bilim Dalı
DOÇ. DR. HAMİT MİRTAGİOĞLU
DR. ÖĞR. ÜYESİ CANAN DEMİR