twitnest: มาดู social graph ใน twitter กันเถอะ

นี่คือกราฟของเพื่อนๆ ผมใน twitter ครับ เส้นเชื่อมบ่งบอกว่า ใคร follows ใครบ้าง
ถ้าอยากลองดูกราฟของคุณบ้าง ลองเข้าไปที่ http://twitnest.appspot.com/

ความสามารถของ twitnest 0.1
- Who knows who? – คลิกคนที่คุณอยากรู้ว่าเขา follows ใครบ้าง
- Auto-group – ช่วยจัดกลุ่มคนในกราฟอัตโนมัติ เวลาใช้ก็คลิกปุ่มแล้วก็เลื่อน slider ไปทางขวาเรื่อยๆ จนได้จำนวนกลุ่มที่พอใจ (เลือกได้ว่าอยากได้กลุ่มมากๆ หรือน้อยๆ) โดยคนที่มีชื่อสีเดียวกันคือคนที่อยู่กลุ่มเดียวกัน

วิธีควบคุม
- drag กราฟไปมาเพื่อเลื่อนตำแหน่งที่ดูได้
- scroll mouse wheel เพื่อซูมเข้าซูมออก
- drag คนในกราฟเพื่อเปลี่ยนตำแหน่งได้ครับ

เมื่อคืนหักดิบ ปั่นให้เสร็จเพื่อที่จะเอาลงเน็ตให้คนอื่นได้ลองใช้ซักที (หลังจากดองเค็มไว้ในเครื่องนานกว่า 4 เดือน)
ถ้าเล่นแล้วมี comment หรือจะรายงาน bug ขอให้ทิ้งข้อความไว้ให้ @nattster หรือที่ blog นี้ได้เลยครับ

ตั้งแต่ตรงนี้เป็นต้นไปเป็นรายละเอียด(ทางเทคนิค) เกี่ยวกับโปรแกรมครับ ถ้าสนใจค่อยอ่านต่อละกันครับ

มันทำงานยังไง?
มันจะโหลดรายชื่อ follows ทั้งหมดใน twitter มา จากนั้นมันก็จะโหลดต่อไปเรื่อยๆ เพื่อดูว่า ใคร follows ใครบ้าง
ตอนนี้โปรแกรมถูกจำกัดให้แสดงผลเฉพาะ 70 คนที่มีคน follows มากที่สุด (ดังนั้นในกราฟของบางคนจะเห็นว่ามันติดกันเป็นตังเม)

โปรแกรมจัดตำแหน่งโหนดในกราฟอัตโนมัติโดยใช้ Forced-based algorithms ซึ่งผม implement ได้แย่มาก O(n^3) กราฟถึงจะถือว่าจัดเสร็จ แต่โชคดีที่มันแสดงผลระหว่างจัดให้ดูสดๆ ได้ (ความจริงมีวิธี implement ให้ดีกว่านี้แต่… โอ้ คงต้องใช้เวลานั่งเขียนอีกนาน)

Auto-group คือตัวจัดกลุ่มคนอัตโนมัติ ผมอยากได้ความสามารถนี้มาก เพราะบางทีคนที่มา follows เราเนี่ยเรายังไม่รู้จักเขาเลย (หรือจำไม่ได้เพราะไม่รู้ว่าชื่อในเน็ตของเค้าคืออะไร) ผมคิดว่าถ้าเราเห็นว่าคนนั้นเขาอยู่ในกลุ่มคน เราน่าจะจำ/นึกออกได้ง่ายขึ้นว่าเขาคือใคร วิธีจัดกลุ่มอัตโนมัติเกิดจากการพยายาม merge คน 2 คนเป็นกลุ่มเดียวกัน และ merge ซ้ำไปเรื่อยๆ ดังนั้นเราจะได้ dendogram ออกมาดังภาพต่อไปนี้ พอมาดู dendogram ดีๆ จะเห็นว่าที่ level สูงๆ จะเริ่มมีกลุ่มที่ใหญ่ขึ้นเรื่อยๆ ตอนนี้ใน twitnest เนี่ยให้ผู้ใช้เป็นคนลาก slider เพื่อควบคุมว่าจะจัดกลุ่มมากน้อยแค่ไหน (ความจริงควรทำให้ user-friendly กว่านี้)

ref: http://en.wikipedia.org/wiki/Dendrogram

ส่วนวิธี merge คน 2 คน หรือกลุ่ม 2 กลุ่มเข้าด้วยกัน นี่ดูจากจำนวน edge ภายในกลุ่มนั้นว่าสูงกว่า จำนวน edge แบบ random ในกราฟทั่วไปมั้ย ถ้าเกิดว่ามากกว่าก็ถือว่าควรอยู่กลุ่มเดียวกันได้ – -” (เฮือก… อธิบายแบบนี้จะเข้าใจมั้ยเนี่ย) วิธีที่ใช้นี้อ่านมาจาก งานเมื่อปี 1997 ของ อ.ฟิสิกส์ท่านนึง (จำชื่องานมิได้ T_T เดี๋ยวหาเจอแล้วจะเอามาแปะครับ)

สรุปว่าตอนนี้โปรแกรมยังทำอะไรไม่ได้มาก ถ้าหากใครอยากได้ feature อะไร (เหมือนเดิมครับ) ช่วยบอกด้วยนะครับ ช่วงปิดเทอมนี้จะได้นั่งทำต่อ (ถ้ายังมีคนสนใจโปรแกรมนี้อยู่หนะนะ)

ไปนั่งอ่านหนังสือสอบพรุ่งนี้ต่อก่อนละคร้าบ