ผลต่างระหว่างรุ่นของ "Sgt/eigen1"

จาก Theory Wiki
ไปยังการนำทาง ไปยังการค้นหา
 
(ไม่แสดง 10 รุ่นระหว่างกลางโดยผู้ใช้ 5 คน)
แถว 1: แถว 1:
 +
<noinclude>{{Sgt/เนื้อหา}}</noinclude>
 +
 
== โค้ดตัวอย่าง ==
 
== โค้ดตัวอย่าง ==
  
แถว 14: แถว 16:
 
การปรับแก้การแสดงผล:
 
การปรับแก้การแสดงผล:
  
* สามารถปรับการแสดงโหนดโดยดูจากเอกสารฟังก์ชัน scatter [http://matplotlib.org/api/pyplot_api.html#matplotlib.pyplot.scatter scatter]
+
* สามารถปรับการแสดงโหนดโดยดูจาก [http://matplotlib.org/api/pyplot_api.html#matplotlib.pyplot.scatter เอกสารฟังก์ชัน scatter]
* สามารถแก้ไขรูปแบบเส้นโดยดูจากวิธีการเพิ่มเส้นในการ plot โดยใช้ LineCollection [http://matplotlib.org/api/collections_api.html#matplotlib.collections.LineCollection LineCollection]
+
* สามารถแก้ไขรูปแบบเส้นโดยดูจาก [http://matplotlib.org/api/collections_api.html#matplotlib.collections.LineCollection วิธีการเพิ่มเส้นในการ plot โดยใช้ LineCollection]
  
 
=== โปรแกรมหลัก main.py พร้อมคำอธิบาย ===
 
=== โปรแกรมหลัก main.py พร้อมคำอธิบาย ===
แถว 51: แถว 53:
  
 
ทดลองใส่กราฟในรูปแบบต่าง ๆ เช่น tree, cycle, complete graphs, grids เป็นต้น แล้ววาดโดยใช้ eigenvector ที่สองและสาม
 
ทดลองใส่กราฟในรูปแบบต่าง ๆ เช่น tree, cycle, complete graphs, grids เป็นต้น แล้ววาดโดยใช้ eigenvector ที่สองและสาม
 +
 +
<gallery class="center" widths="320px" heights="240px">
 +
 +
  ไฟล์:Sgt_lab1_k11.png | Complete graph ขนาด 11 โหนด
 +
 +
  ไฟล์:Sgt_lab1_bipartite.png | Bipartite graph ขนาด 20 nodes แบ่งเป็น A,B ข้างละ 10 nodes โดยที่ node ใดๆในฝั่ง A เชื่อมไปยังทุก node ในฝั่ง B
 +
 +
  ไฟล์:Plot_ring_star_150.png | Graph ที่มี topology เป็น star ผลม ring ขนาด 150 nodes ต่อเป็น 1 cycle ที่ประกอบด้วย 149 nodes และให้ 1 node เชื่อมไปยังทุก node ที่เหลือ
 +
 +
  ไฟล์:Graph_plot_grid81x40.png | Graph ที่มี topology เป็น grid ขนาด 81x40 โดยมีการเชื่อมต่อ node เว้น node (function eig(la) ใช้เวลาคำนวณนานประมาณ 10 นาที)
 +
 +
</gallery>
  
 
== การทดลอง Graph Partitioning ==
 
== การทดลอง Graph Partitioning ==
 
=== Synthetic data ===
 
=== Synthetic data ===
 +
 
=== Image data ===
 
=== Image data ===

รุ่นแก้ไขปัจจุบันเมื่อ 19:02, 2 กุมภาพันธ์ 2558

Spectral Graph Theory

  1. บทนำและทบทวนพีชคณิตเชิงเส้น (ณัฐวุฒิ)
  2. คุณสมบัติของ Eigenvalue ต่อกราฟ (ธานี,ณัฐวุฒิ)
  3. คุณสมบัติของ Eigenvalue ต่อกราฟ[2] (ภัทร)
  4. คุณสมบัติของ Eigenvalue ลำดับที่สองบนกราฟต่างๆ (ธานี)
  5. Cheeger Inequality (ศุภชวาล)
  6. การทดลอง Cheeger Inequality และ Effective Resistance (ธานี)
  7. Random Walks และ Psuedo Random Generator (ศุภชวาล)
  8. Psuedo Random Generator[2] (ภัทร)
  9. Coding Theory และ Expander code (ธานี)
  10. Expander graph from Linear coding (ภัทร)
  11. Chebyshev polynomial (ศุภชวาล)
  12. Preconditioning (ธานี)

แก้ไขกล่องนี้แก้ไขสารบัญ

โค้ดตัวอย่าง

  • โค้ดตัวอย่างอยู่ที่ github
  • Modules:
    • mat.py: สร้าง adjacency matrix และ degree matrix
    • generators.py: สร้าง adjacency list ของ line และ random graph แบบสอง cluster
    • grpplot.py ส่วนของการ plot
    • main.py: โปรแกรมหลัก

ฟังก์ชัน grpplot.plot

ฟังก์ชัน grpplot.plot(n, adjmat, px, py) จะวาดกราฟ n โหนด ตาม adjacency matrix adjmat โดยใช้พิกัดจาก px และ py

การปรับแก้การแสดงผล:

โปรแกรมหลัก main.py พร้อมคำอธิบาย

def main():
    # สร้าง adjacency list ของกราฟ
    n = 100
    #adjlist = gen_line(n)
    adjlist = gen_random(n,500)

    # สร้าง laplacian ของกราฟ
    a = adjmat(n,adjlist)
    d = degmat(n,adjlist)
    la = d - a

    # คำนวณ eigenvectors, eigenvalues แต่ผลจาก eig ไม่เรียง เลยจับมาเรียงเองด้วย sort_eig
    w,v = eig(la)
    w,v = sort_eig(w,v,n)
    print w

    # eigenvectors ของ $\lambda_2$ และ $\lambda_3$
    e2 = v[1]
    e3 = v[2]

    # แกน x เอามาจาก eigenvectors, แกน y สุ่ม
    px = [e2[i,0] for i in range(n)]
    py = [random() for i in range(n)]

    plot(n,a,px,py)
    raw_input()

การทดลอง Graph drawing

ทดลองใส่กราฟในรูปแบบต่าง ๆ เช่น tree, cycle, complete graphs, grids เป็นต้น แล้ววาดโดยใช้ eigenvector ที่สองและสาม

การทดลอง Graph Partitioning

Synthetic data

Image data