Budapesti Műszaki és Gazdaságtudományi Egyetem
Természettudományi Kar		 Tantárgy Adatlap
Tantárgy kód BMETE95MM40
Tantárgy azonosító adatok
1. A tárgy címe Spektrális klaszterezés
2. A tárgy angol címe Spectral Clustering
3. Heti óraszámok (ea + gy + lab) és a félévvégi követelmény típusa 2 + 0 + 0 v Kredit 3
4. Ajánlott/kötelező előtanulmányi rend
vagy Tantárgy kód 1 Rövid cím 1 Tantárgy kód 2 Rövid cím 2 Tantárgy kód 3 Rövid cím 3
4.1
4.2
4.3
5. Kizáró tantárgyak
6. A tantárgy felelős tanszéke Sztochasztika Tanszék
7. A tantárgy felelős oktatója Dr. Bolla Marianna beosztása egyetemi tanár
Akkreditációs adatok
8. Akkreditációra benyújtás időpontja 2020.04.19. Akkreditációs bizottság döntési időpontja 2020.04.21.
Tematika
9. A tantárgy az alábbi témakörök ismeretére épít
Elemi gráfelmélet, elemi valószínűségszámítás, lineáris algebra
10. A tantárgy szerepe a képzés céljának megvalósításában (szak, kötelező, kötelezően választható, szabadon választható)
TTK Matematikus és Alkalmazott matematikus MSc képzés szabadon választható tárgya
11. A tárgy részletes tematikája

Gráf alapú mátrixok bevezetése kvadratikus elhelyezési problémák megoldásához. Nevezetes egyszerű gráfok, továbbá él- és csúcssúlyozott gráfok Laplace- és modularitás-mátrixainak spektruma. Többszempontú vágások minimalizálása és maximalizálása a bevezetett mátrixok sajátértékeievel; az optimumhoz közeli vágások megkeresése a sajátvektorokkal történő reprezentánsok metrikus klaszterzésével (k-közép algoritmus és súlyozott változatai). A módszerek általánosítása nemnegatív elemű téglalapmátrixokra és diszkrét együttes eloszlásokra SVD-vel. Reprodukáló magú Hilbert-terek elmélete. Nagyméretű, zajos hálózatok blokk-struktúrájának feltárása, perturbációs tételek. Tesztelhető gráfparaméterek, a Lovász László és társszerzői által bevezetett definíciók alkalmazása a többszempontú vágásokra. Véletlen gráf modellek, sztochasztikus blokkmodellek, paraméterek becslése az EM-algoritmussal.

Introducing graph based matrices for the solution of quadratic placement problems. Laplacian and modularity spectra of some notable simple graphs and that of edge- and vertex-weighted graphs. Estimating minimal and maximal multiway cuts with the spaectra of the above matrices; finding near optimal cuts with metric clustering of the representatives assigned to the vertices by means of the eigenvectors (k-means algorithm and its weighted versions). These methods are generalized to rectangular arrays of nonnegative entries and to discrete joint distributions via SVD. Theory of Reproducing Kernel Hilbert-spaces. Revealing the underlying block-structure in large, noisy networks; perturbation theorems. Testable graph parameters, applying the definitions of László Lovász and his coauthors to multiway cuts. Random graph models, stochastic block models, parameter estimation with the EM algorithm.
12. Követelmények, az osztályzat (aláírás) kialakításának módja
szorgalmi
időszakban		 Zárthelyi dolgozatok és házi feladatok, melyeknek külön-külön 40%-os teljesítése szükséges az aláíráshoz. vizsga-
időszakban		 Szóbeli vizsga elméleti kérdésekkel és a fontosabb tételek bizonyításával. A félévközi eredmény és a vizsga eredménye 50-50%-ot képvisel az érdemjegy kialakításában.
13. Pótlási lehetőségek
Pót zh a pótlási héten
14. Konzultációs lehetőségek
Az előadó fogadóóráján
15. Jegyzet, tankönyv, felhasználható irodalom
Bolla, M., Spectral Clustering and Biclustering. Learning Large Graphs and Contingency Tables. Wiley, 2013.
Chung, F., Spectral Graph Theory, CBMS Regional Conference Series in Mathematics, 92. American Mathematical Society, 1997.
16. A tantárgy elvégzéséhez átlagosan szükséges tanulmányi munka mennyisége órákban (a teljes szemeszterre számítva)
16.1 Kontakt óra
28
16.2 Félévközi felkészülés órákra
14
16.3 Felkészülés zárthelyire
10
16.4 Zárthelyik megírása
2
16.5 Házi feladat elkészítése
14
16.6 Kijelölt írásos tananyag elsajátítása (beszámoló)
0
16.7 Egyéb elfoglaltság
0
16.8 Vizsgafelkészülés
22
16.9 Összesen
90
17. Ellenőrző adat Kredit * 30
90
A tárgy tematikáját kidolgozta
18. Név beosztás Munkahely (tanszék, kutatóintézet, stb.)
Dr. Bolla Marianna
egyetemi tanár
Sztochasztika Tanszék
A tanszékvezető
19. Neve aláírása
Dr. Simon Károly