標題: PLPF: 探勘網路行為履歷於連線行為預測
PLPF: A Profile-based Link Prediction Framework in a Time-evolving Graph
作者: 李政輝
Lee, Zheng-Hui
彭文志
李素瑛
Peng, Wen-Chih
Lee, Suh-Yin
資訊科學與工程研究所
關鍵字: 連線行為預測;連線行為履歷;演進圖;link prediction;profile;evolving graph
公開日期: 2010
摘要: 人們的生活中處處充滿了不同的連結行為,例如連上網站漫遊、寄信給朋友或是打電話給友人等。這些連結行為最適合透過演進圖來觀察使用者的連結現象。假設我們有一個持續紀錄使用者連結行為的日誌,則當一個不同的連結對象出現時,我們可能會相當好奇還有那些使用者也會跟這個新的對象建立連結。 在這裡,我們提出了一個預測新連線行為的架構。透過持續紀錄、更新使用者的連結行為履歷,我們可以了解使用者的喜好與興趣,並以此為基準預測新的連線行為。我們的中心想法是:如果使用者與他人有一致的喜好或興趣,則他們有很大的可能會與相同的對象建立連結,當然也包括了新出現的連結對象。在這裡,我們不止紀錄使用者的常態連結行為於其履歷,同時也紀錄了使用者最近才有的、不同以往的連結行為。 我們用了一個現實生活中的連結資料來驗證我們的想法,並與目前最新、最好的方法進行比較。實驗結果顯示,我們的方法不僅比已知最新、最好的方法有更好的效能,而且擁有更少的計算時間,不 會隨著的歷史資料的長度而增加。除此之外,我們了解到預測這類新的連結行為時,觀察使用者最近改變的興趣、喜好,比觀察使用者長久以來的興趣、喜好來得有用。
Connection logs are widely used to record connection behavior between sources and des- tinations, such as users and sites in the internet network, and are best represented as an evolving graph to illustrate the evolving connection behavior of users. Given a continuously recording connection log, when a new destination appears (i.e., connected by a few sources initially), one may want to know who else will then likely to connect it. In this work, we propose a framework using profiles of sources to predict the top-k possible links to the specific destination from k different sources which have never connected to it before, where a profile records the connection behavior of a source including the static and surprising features to represent his/her long-term and short-term interests. The concept behind our framework is that sources have similar connection behavior before are likely to have similar connection behavior after, hence sources having similar profiles as the first source who connects to the new destination are best candidates to connect the same destination later. In the experiment, we use a real dataset of the internet network to evaluate the perfor- mance of our method, and compare it to the state-of-the-art method driven by information flow [20]. It shows that our method has improvement in the effectiveness while comparing to the previous method, and our method has a consistent computation time cost rather than the increasing computation time cost using previous method while the whole connection log increases. Furthermore, we show that surprising features of connection behavior are much more useful when predicting new links in the internet network.
URI: http://140.113.39.130/cdrfb3/record/nctu/#GT079755554
http://hdl.handle.net/11536/45900
Appears in Collections:Thesis


Files in This Item:

  1. 555401.pdf