複雜關係圖的可視化
By Mountain • Oct 18th, 2007 • Category: 技術話題
儅我們擁有成千上萬的人與人的關係數據之後，如何才能把這些數據以合適的圖形方式呈現給大家呢？直觀的講，關係近的這些人應該聚在一起，而關係遠的人在圖上也離得比較遠。雖然沒有嚴格的證明，但我們尋找到一種動力學方法來產生這樣的圖形。
假想圖中的節點都分佈在一個平面上，每一個節點都有它的位置。節點與節點之間有一種作用力—儅距離比較近時，表現為排斥；距離很遠時，表現為吸引力。另一方面，圖中的邊，相當於兩個節點上加裝了彈簧，距離越遠引力越大。在有了這種節點和節點作用之後，圖就可以自然演化。但爲了避免讓圖的演變無法終止，我們可以再引入摩擦力來耗損能量，摩擦力的大小只和速度有關係，方向和速度相反。當圖中所有節點的速度小於指定的閾值演化就終止。
在上述算法下，我們很容易就把複雜關係圖可視化呈現出來。這個算法的内存開銷比較小，是|V|+|E|的常數倍；而時間開銷有兩個因素：一個是演化每一步的計算量，這個是|V|^2+|E|的常數倍；另一個是演化本身到終止需要多少步，根據經驗需要的步數大致是ln|V|的常數倍。
這裡圖表顯示了一個幾千個節點的計算過程，縂的耗時大概用來三個小時。
Mountain is
Email this author | All posts by Mountain
这个算法很像分子动力学啊，可以试一试能量优化的方法，不带速度，计算某一个构象的能量和梯度，沿着梯度方向改变构象一小步再计算能量和梯度直到梯度小于阈值。
我是上海的Eddie.最近我正在和一群朋友研究Wiki,实在找不到你的联系方式.方便的话,可否通过留言的邮件地址和我联系?
这位仁兄，都转型做互联网了，就花心思改改这背景颜色吧。