veri madenciliği

Transkript

veri madenciliği

Sosyal İlişkiler: Çizge

VERİ MADENCİLİĞİ

Sosyal Ağlar
Düğümler: Kişiler
Ayrıtlar: sosyal
ilişkiler



Yrd. Doç. Dr. Şule Gündüz Öğüdücü
http://www3.itu.edu.tr/~sgunduz/courses/verimaden/


aile, arkadadaş, iş
Çizge G(V,E)
V: düğümler
kümesi
E: Ayrıtlar kümesi
Benzerlik Matrisi
S. Milgram (1967)
Yakınlığın Altı Derecesi: Six Degrees of Separation
1
Sosyal Ağ


4
Kevin Bacon Oyunu
Sosyal ağ kişiler arasındaki ilişkilerin
oluşturduğu bir yapıdır
Sosyal ağ incelemesi: ağ yapısının, kişiler ya da
gruplar (topluluklar) arasındaki ilişkilerin ve
bilgi akışının incelenmesi



1994 yılında bir grup öğrenci
tarafından icat edildi: Craig
Fass, Brian Turtle, Mike Ginelly
Amaç: Bütün oyuncuları en az
sayıda bağlantı ile en kısa
sürede Kevin Bacon’a
bağlamak
Oracle of Bacon Web sitesi
IMDB veritabanındaki veriyi
kullanarak iki oyuncu
arasındaki en kısa yolu
buluyor.
http://oracleofbacon.org/
L.C. Freeman, Visualizing Social Networks. Journal of Social Structure, 2000.
2
Sosyal İlişkiler: Çizge

Sosyal Ağların Özellikleri
Düğümler: Kişiler

Farklı (doğal) ağlar

Ortak özellikleri







3
sosyal, biyolojik, teknik, içerik..
Çok büyük, dinamik: düğümler, ayrıtlar
eklenebilir/silinebilir
düğümler hangi düğümlerle ilişkide olacaklarına kendileri
karar veriyorlar
düğümler arası etkileşim ayrıtlarla sınırlı
uzaklık/benzerlik için soyut bilgi: coğrafi, içerik, ilişkiler
Sosyal ağ kuramı: link analizi

5
Farklı ağların genel özellikleri nelerdir?
Bu özellikler nasıl belirlenir, nasıl ölçülür?
6
1

Uzunluk (dG(s,t)): Iki düğüm (s,t) arasındaki en büyük,
en küçük, ortalama uzaklık






Iki düğüm arasında bulunan yoldaki ayrıt sayısı
Iki düğüm arasında bulunan yoldaki ayrıtların
ağırlıklarının toplamı
Derece: yönlü ise düğüme gelen (in-link) / düğümden
çıkan (out-link) bağlantıların sayısı
Merkez: Ağdaki diğer düğümlerin bağlı olduğu bir ya
da bir kaç düğüm
Yoğunluk: Ağdaki bağlantı sayısının olası bütün
bağlantı sayısına oranı

=9/21
7



t

st= ts s ve t (s,t  V) düğümleri arasındaki en kısa yol sayısı -> ss=1
st(v): v  V düğümünün üzerinde bulunduğu s ve t düğümleri arasındaki
en kısa yol sayısı
Cc ( v ) 
Iki düğüm arasında
bulunan yoldaki ayrıt
sayısı
d
tV
CG (v) 
dG(s,t) = 3 (en kısa yol)

10
Tanımlar
s
Uzunluk (dG(s,t)): Iki
düğüm (s,t) arasındaki
en büyük, en küçük,
ortalama uzaklık
Merkez: Ağdaki diğer
düğümlerin bağlı
olduğu bir ya da bir
kaç düğüm
Yoğunluk: Ağdaki
bağlantı sayısının
olası bütün bağlantı
sayısına oranı
Cs (v ) 
Iki düğüm arasında
bulunan yoldaki
ayrıtların ağırlıklarının
toplamı
1
( v, t )
1
max tV d G (v, t )

s  v  tV
C B (v ) 
closeness centrality (Sabidussi, 1966)
G

s  v  tV
st
(v )
 st (v)
 st
graph centrality (Hage and Harary, 1995)
stress centrality (Shimbel, 1953)
betweenness centrality
(Freeman, 1977; Anthonisse, 1971)
Ulrik Brandes, A Faster Algorithm for Betweenness Centrality, Journal of Mathematical Sociology
25(2):163-177, (2001).
8

Tanımlar
Derece:


yönlü ise düğüme
gelen (in-link) /
düğümden çıkan
(out-link)
bağlantıların sayısı
yönsüz ise düğüme
bağlanmış ayrıt sayısı
11


n
Hizip (Clique):
 seçilebilecek her düğüm çifti arasında
bir bağ olan alt çizge
 tam bağlı alt çizge
Daha zayıflatılmış
 N-Hizip (N-Clique): Bir düğümün içinde bulunduğu alt çizgedeki
diğer tüm düğümlere olan uzaklığı en çok N olabilir
 N-Klan (N-Clan): N-Hizipteki düğüm çiftleri arasındaki yollar
üstündeki düğümler de N-Hizip üyesi
 K-Plexes: Bir düğümün n düğümden oluşan bir N-Hizip içindeki en
az n-k düğüm ile doğrudan bağlı olması
d(n)=4
9
12
2
Tanımlar

Problemler
Kesitleme noktası (Cut Points): Bağlı olan bir
G çizgesinden, v düğümü ve bu düğüme
bağlı olan bütün ayrıtlar çıkarıldığında oluşan
G-v çizgesi bağlı değil ise v kesitleme
noktasıdır.

Bağlı parçalar:

Ağ çapı:







5
1


7
2
6
Gruplaşan ilişkiler/düğümler
Örtüşen gruplar
Grup içi ve gruplar arası ilişkilerin oranı
Grup içi ve gruplar arası ilişkilerin rolü
Ağın yapısı

4
en uzak – ortalama
Bağlı olmayan düğümler / parçalar
Küçük dünya özelliği
Demetleme

Kesitleme noktası
kaç parça, büyüklükleri ne, ne kadar bağlılar
düğümlerin derecesi


3

13
Web’de Sosyal Ağlar
Kesitleme noktası (Cut Points): Bağlı olan bir
G çizgesinden, v düğümü ve bu düğüme
bağlı olan bütün ayrıtlar çıkarıldığında oluşan
G-v çizgesi bağlı değil ise v kesitleme
noktasıdır.
5
1
6
2
16
Tanımlar

ki: i düğümünün derecesi, Ni: i düğümünün komşular kümesi
ilişkilerin ağırlığının dağılımı
ağ içinde önemli rolü olan düğümler: iki grubu birbirine bağlayan
4
3
14
Facebook
Myspace
 LinkedIn
 Classmates
 Orkut
 Bebo
Medya paylaşım siteleri:
 YouTube
 Flickr


17
Sosyal Ağların Yeteneği
Özellik
Tanım
Etki
Derece
(Degree)
Bir düğümün bağlantı sayısı
daha fazla seçenek
Yakınlık
Diğer düğümlere olan
yolun uzunluğu
Diğer düğümlerle doğrudan
etkileşim
İki düğüm arasında yer
alan düğüm
Diğer iki düğüm arasında
ilişkiye sağlamak/kesmek
Ara düğüm
15
Boyd, D. M., & Ellison, N. B. (2007). Social network sites: Definition, history, and scholarship.
Journal of Computer-Mediated Communication, 13(1), article 11.
http://jcmc.indiana.edu/vol13/issue1/boyd.ellison.html
18
3
Sosyal Ağlar için Modeller

Demetleme Katsayısı
Rassal çizgeler (Random Graphs: Erdös-Rényi

C7=2*0/2*1=0
C1=2*1/3*2=1/3
C2=2*1/2*1=1
models)

Watts-Strogatz modelleri

Scale-free Networks
Demetleme katsayısı
5
1
7
6
2
4
3
19
N = 12
Rassal Ağlar

Erdös-Rényi (ER)
Model: 1959 yılında
Paul Erdös ve Alfred
Rényi



Erdös-Rényi Model (1960)
p = 0.0 ; k = 0
N: Düğüm sayısı
p: iki düğüm arasında
ayrıt olma olasılığı

Poisson distribution
(1913-1996)
Ortalama derece:
p = 1.0 ; k ≈ ½N2
20
Rassal Ağlar
N(N-1)/2 adet hileli yazı tura atma
Derece dağılımı
 N çok büyük olduğunda Poisson
dağılımı
 G(N,p) ile bir çizge oluştur,
rastgele bir u düğümü
 Pr[deg(u) = k] ?
 Poisson dağılımı ortalama
= p(N-1) ~ pN
Demetleme katsayısı (clustering
coefficient ) küçük
23
Erdös Sayısı

Paul Erdös ile birlikte
makale yazma uzaklığı


f (k ;  ) 

Pál Erdös
p=1/6
N=10
~1.5
p = 0.09 ; k = 1

Connect with
probability p
p = 1/2N, p = 1/N, p
= 2/N, p=10/N, p =
log(N)/N...
k ≈ pN

22
Ci 
2 e jk 
ki (ki  1)
k e  
k!

: v j , vk  N i , e jk  E
makale yazan kişinin
Erdös sayısı=1
makale yazan bir kişiyle
birlikte makale yazan
kişinin Erdös sayısı=2
Yaklaşık 1500’den fazla
makalesi var
http://www.oakland.edu/enp/
N
C   Ci
i 1
21
24
4
Watts-Strogatz modelleri: Caveman and
Solaria




Watts-Strogatz Model
Erdos-Renyi
 Ortak komşuları olması iki düğüm arasında ayrıt olma olasılığını
artırmıyor
 her ayrıt daha öncekilerden bağımsız olarak oluşuyor
Gerçekte oluşan ağ yapısına uygun değil
 iki kişinin tanışma olasılığı ortak arkadaşları varsa daha fazladır
 Web de iki sayfa biribirine bağlı ise büyük olasılıkla aynı
konudadırlar
Watts Caveman:
 ayrıtların genel olarak yoğunluğu az
 iki düğümün ortak komşuları varsa aralarında ayrıt olma olasılığı
büyük
Watts Solaria
 ayrıtların genel olarak yoğunluğu az, bir düğümün komşuları
arasında ayrıt olma olasılığı farklı değil
 Erdos-Renyi çizgesine benzer




25
Bir daire etrafında eşit dağılmış N düğüm
Her düğümün en yakın k komşusu arasında k ayrıt (yakın ilişki)
p olasılığı ile bir düğüme az sayıda rastgele ayrıt ekle (uzak ilişki)
farklı p değerleri için farklı çizgeler
Collective dynamics of 'small-world' networks
Duncan J. Watts & Steven H. Strogatz
-model



Small Worlds - Occam’s Razor
Gerçek hayatta çizgelerde düğümler arasındaki bağlantılar düzenli
çizge (regular graph) ve rassal çizge arasında
Gerçek hayattaki sosyal ağların yapısını mıodellemek
 -model (Watts, D. J. (1999) Kevin Bacon, the small-world, and
why it all matters. Santa Fe Institute Bulletin, 14(2): center
section)
-model için parametreler
 N düğüm sayısı
 k: ortalama derece
 p: iki düğüm arasında ayrıt olma olasılığı
 : yakın ilişkilerin olasılığını artırmak için parametre


küçük  değerleri için demetleme katsayısı
büyük





demetleme katsayısı büyük
Örnek
u,v düğüm çifti için
 m(u,v): ortak komşu sayısı
R(u,v): iki düğümün arasında ayrıt olma eğilimi (propensity)
 m(u,v) >= k, R(u,v) = 1
 m(u,v) = 0, R(u,v) = p
 diğer durumlarda R(u,v) = p + (m(u,v)/k)^ (1-p)

üç gerçek ağ üzerinde inceleme



Oyuncular
batı bölgesindeki güç santralleri
C.elegans sinir sistemi
 için Erdös-Renyi çizgelerine benziyor
Actors
Power-grid
C.elegans
29
-model

farklı özellikler için basit tek bir model
Watt’s small world:
 çapı küçük

26
Erdos-Renyi  çapı küçük
-model  büyük demetleme katsayısı
Occam’s Razor


Rassal ağlarda olduğu gibi iki düğüm arasına ayrıt eklenir. Ancak iki düğümün
ortak komşuları varsa aralarında ayrıt olma olasılığı fazladır.
28
27
n
k
d
c
225,226
4,941
282
61
2.67
14
3.65
18.7
2.65
0.79
0.08
0.28
30
5
Small World


Topluluk Belirleme
Rastgele iki düğüm arasındaki yolun uzunluğu
kısa
Serbest Ölçekli Ağlar (Scale free): Örnek web




S. Fortunato and C. Castellano, Community Structure
in Graphs, ArXiv e-prints
Bir çizge içinde ortak özellikleri/görevleri olan
düğümler topluluğu

düğümler web sayfaları
ayrıtlar bağlantılar




Topluluk içindeki topolojik konumlarına göre düğümler
sınıflandırılabilir


31
Metabolik

web: yeni sayfalar/siteler ekleniyor/siliniyor
yayınlar: yeni yayınlar ekleniyor
Eklenen düğümlerle oluşan ayrıtlar üniform değil


Sosyal
35
32
Serbest Ölçekli Ağlar
Topluluk Tanımı
Pareto veya power law

dağılımı

P(k)=Ck-


çapı küçük (~log(N))
demetleme katsayısı çok
büyük değil


Ekonomik
çok sayıda sayfanın/sitenin bağlantı verdiği
sayfaya/siteye bağlantı verme olasılığı yüksek
çok sayıda yayının referans gösterdiği yayının referans
gösterilme olasılığı yüksek

Protein
Ağ sürekli yeni düğümlerin eklenmesi/silinmesi ile
değişiyor


34
Düğüm sayısı N sabit değil


topluluğun merkezinde yer alan düğüm
topluluğun sınırında yer alan düğüm
Serbest Ölçekli Ağlar

aynı konudaki web sayfaları
benzer işleve sahip proteinler
aynı konuda çalışan insan grupları
aynı ilgi alanına sahip insan grupları
Dar tanım
Geniş tanım
Düğüm benzerliği
yakın komşuları ile ayrıt olma
olasılığı yüksek değil
“hub” olan düğümlerle ayrıt
oluşturma olasılığı yüksek
33
36
6
Dar Tanım

Çizge Parçalama
Sadece alt çizgedeki ilişkilere göre toplulukları
belirliyor.


Örnek: Hizip, n-klan, k-plexes
Graph Partitioning: Çizgeyi bir düğüm bir
grupta kalacak şekilde gruplara (altçizgelere)
bölme
Problem:


37
Geniş Tanım




40
Örtüşen Topluluklar
Topluluk çizginin yapısal bir birimi
Altçizgeler hem kendi içindeki ilişkiler hem de
çizgenin geri kalanıyla olan ilişkileri ile
belirleniyor
Null model: içinde topluluk bulunmayan çizge

Örtüşen topluluklar
Hiyerarşik yapı

Erdös-Renyi
Newman-Girvan: düğümlerin orjinal çizge ile
aynı dereceye sahip olduğu rassal çizge
Gerçek dünyada bir nesne birden fazla gruba
üye olabilir
G. Palla, I. Derényi, I. Farkas, T. Vicsek,
Uncovering the overlapping community structure of
complex networks in nature and society
Nature 435, 814, 2005
http://www.cfinder.org/
38
Düğüm benzerliği

Hiyerarşik Yapı
Düğümler birbirine “benzer” ise aynı toplulukta


41

dar
geniş
Altçizgeler tekrar
parçalanabilir
A. Clauset, C. Moore, M.E.J. Newman,
Hierarchical structure and prediction of missing links
Nature 453, 98, 2008
39
42
7
Çizge Parçalama

Girvan-Newman Algoritması
Hangisi daya iyi


M. Girvan & M.E.J Newman, Community
structure in social and biological networks,
PNAS 99, 7821-7826 (2002)
Toplulukları birbirine bağlayan ayrıtları belirle



43

1.
2.
3.
4.
44
Bütün ayrıtların “betweenness” değerleri
hesaplanır
En büyük “betweenness” değerine sahip ayrıt
silinir
Kalan ayrıtların “betweenness” değerleri
hesaplanır
2. adıma geri dönülür
Birimsellik

Modularity:
Bitişiklik Matrisi:
m

1 (u,v)  E
Auv  
0 diger
Phys. Rev. E 69, 026113 (2004)
2.
vV
C  {c1 , c2 ,...}, ci  c j   (i  j )  ci  V
3.
ci C
A
uci ,vc j
uv
M.E.J. Newman & M. Girvan, Finding and
evaluating community structure in networks,
1.
ku   Auv
eij 
47
Geliştirilmiş Girvan-Newman Algoritması
Auv
2

u , vV
46
Girvan-Newman Algoritması
Üstünlüklerini karşılaştırmak için bir kriter Q
Q(P1) > Q(P2) veya Q(P1) < Q(P2) ?
birbirinden ayrık demetler
İki Farklı Sonuç

Betweenness
bu ayrıtları silme
/ 2m
4.
ai   kv / 2m
Her düğüm bir demet
Q değerini en büyütecek iki düğümü birleştir
Bütün düğümler tek demet olana kadar işleme
devam et
En fazla Q değerine sahip demetlemeyi seç
vci
Q(G , C )   (eii  ai2 )
i
45
48
8
Problemler






Örtüşen topluluklar
Yönlü çizgeler
Ağırlıklı çizgeler
Karmaşıklık
Dinamik ağlar
Büyük ağlar
49
9

veri madenciliği

Transkript

Benzer belgeler

06-Demetleme Yöntemleri-2

Hiper Metin Hiper Metin Yazının içine yerleştirilmiş veya gömülmüş

EN KISA YOL - Endüstri Mühendisliği Bölümü

Uluslararası Başvuru Süreci - Fox Valley Technical College

Uluslararası Öğrenciler için Başarının Geçidi - Admissions