PLPF: 探勘網路行為履歷於連線行為預測

PLPF: A Profile-based Link Prediction Framework in a Time-evolving Graph

李政輝(Zheng-Hui Lee)

指導教授 ： 彭文志 ； 李素瑛

國立交通大學/資訊學院/資訊科學與工程研究所/碩士(2011年)

https://doi.org/10.6842/NCTU.2011.00103

摘要

人們的生活中處處充滿了不同的連結行為，例如連上網站漫遊、寄信給朋友或是打電話給友人等。這些連結行為最適合透過演進圖來觀察使用者的連結現象。假設我們有一個持續紀錄使用者連結行為的日誌，則當一個不同的連結對象出現時，我們可能會相當好奇還有那些使用者也會跟這個新的對象建立連結。
在這裡，我們提出了一個預測新連線行為的架構。透過持續紀錄、更新使用者的連結行為履歷，我們可以了解使用者的喜好與興趣，並以此為基準預測新的連線行為。我們的中心想法是：如果使用者與他人有一致的喜好或興趣，則他們有很大的可能會與相同的對象建立連結，當然也包括了新出現的連結對象。在這裡，我們不止紀錄使用者的常態連結行為於其履歷，同時也紀錄了使用者最近才有的、不同以往的連結行為。
我們用了一個現實生活中的連結資料來驗證我們的想法，並與目前最新、最好的方法進行比較。實驗結果顯示，我們的方法不僅比已知最新、最好的方法有更好的效能，而且擁有更少的計算時間，不
會隨著的歷史資料的長度而增加。除此之外，我們了解到預測這類新的連結行為時，觀察使用者最近改變的興趣、喜好，比觀察使用者長久以來的興趣、喜好來得有用。

關鍵字

連線行為預測 ； 連線行為履歷 ； 演進圖

並列摘要

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.

並列關鍵字

link prediction ； profile ； evolving graph

參考文獻

[1] Evrim Acar, Daniel M. Dunlavy, and Tamara G. Kolda. Link prediction on evolving

data using matrix and tensor factorizations. Data Mining Workshops, Inter-

[2] Lada A. Adamic and Eytan Adar. Friends and neighbors on the web. SOCIAL

NETWORKS, 25:211–230, 2001.

recommending links in social networks. In Proceedings of the fourth ACM inter-