臺灣博碩士論文加值系統

研究線上社群網路平台如Facebook，MySpace，twitter等社群網站(Online Social Networks)，有助於了解人際關係形成的模式，目前最流行的線上網路社群平台為FACEBOOK，FACEBOOK已有超過六億多個註冊帳號，但是在研究社群網路(Social Networks)領域的眾多論文當中少有用到現實的數據資料，其原因在於這些實際的資料難以取得。
假設一個網路上的三個節點，第一個節點和另外兩個節點有鏈結(link)連接但另外兩個節點彼此互相沒有相接，在這樣的情況下，我們想要了解共同朋友(第一個節點)如何影響這兩個節點之間是否能夠建立新的鏈結，這兩個節點有a的機率會產生新的鏈結，並且有1-a的機率不建立新的鏈結。我們希望能在一個真實的資料上計算這個a值。
為了取得這些實際的資料來了解上述理論在真實情況下該會是什麼樣子，本篇論文去尋找前人收集過的舊有資料，利用這筆資料計算a值，並且得到了結果。但若如果我們想了解新建立鏈結的屬性，也就是說新增的鏈結是否為local attachment，又或者是global attachment，單純從別人提供的dataset無法知道，也無法看出鏈結的vanish。因此我們設計了一個收集OSNs資料的軟體，有了這樣的軟體，我們可以：
一、 依自己想要的方式來收集網路真實使用者social graph的資料。
二、 觀察一段時間內網路上鏈結的變化。
三、 收集下來的資料可以用來測試algorithms。
我們將這個軟體取名為Web Crawler，利用WEB爬取的方式收集現有的線上網路社群平台(OSN)。並且為了觀察一個真實的動態平衡網路，針對這個方向我們修改了軟體的功能，使它可以觀察社交網路上鏈結的消逝(vanish)和形成(establish)的過程。

Studying Online Social Networks such as Facebook, MySpace, Twitter…etc, will help us understand the formation of relationships between people in social networks. Nowadays, the most popular Online Social Network Sites is Facebook. There have been more than 600 million accounts registered in Facebook. However, few researches has used real-world data in their researches due to difficulties of having these data.
Assume there are 3 nodes A, B, and C in a network graph. Node A is connected to node B and node C, and node B and C are not connected. In this case, Node A is the mutual friend of node B and C, and, more importantly, we focus on how node A affects the probability of establishing a link between B and C. In our definitions, Node B and C will be connected with probability a, and will not be connected with probability 1-a. Our goal is to find out the a value in real-world data.
To acquire these real-world dataset, we have some dataset which are collected by former researchers. Though we calculate the value a and get our results, we are still not able to study the link establishment and link vanishing properties in these dataset, which are provided by other researchers. For this reason, we develop a program to collect information from Online Social Networks. This program has the following features:
1. Collect social graphs in our ways.
2. Observe the changing of network graphs in a period of time.
3. Use collected data to test our new algorithms.
We name this program as Web Crawler, which “crawls” web pages to collect user’s information in OSNs. For observing the ever-changing networks with link establishing and vanishing, we modified the program to collect user information in a period of time and compare it with former collected data.

一 動機與簡介
1.1 背景介紹
1.2 動機
1.3 相關作業
1.4 論文大綱
二 複雜網路
2.1 社群網路
2.2 社群網路模組
三 資料分析
3.1 Minas Gjoka提供的資料
3.1.1 Metropolis-Hastings Random Walk (MHRW)
3.1.2 Facebook資料分析結果
3.2 Alan Mislove提供的資料
3.2.1 四個OSN的資料
3.2.2 Facebook social graph
3.3 取樣程式
3.4 a值計算
四 Web Crawler
4.1 程式架構
4.1.1 程式架設平台
4.2 COM(Component Object Model)
4.3 資料庫
4.4 網頁分析
4.5 取值方法
4.6 演算法
4.6.1 網頁擷取
4.6.2 收集
4.6.3 比較
4.7 判斷共同好友
五 實驗結果
5.1 資料集結果比較
5.2 實驗結果
六 結論與未來方向
6.1 結論
6.2 未來方向

[1] CheckFacebook.com
[2] K. Lewis, J. Kaufman, M. Gonzalez, A. Wimmer, and N. Christakis, Tastes, ties, and time: A new social network dataset using Facebook.com,” Social Networks, 2008.
[3] A. L. Traud, E. D. Kelsic, P. J. Mucha, and M. A. Porter, “Community structure in online collegiate social networks,” 2008, arXiv: 0809.0960.
[4] Minas Gjoka, Michael Sirivianos, Athina Markopoulou, Xiaowei Yang, Poking Facebook: Characterization of OSN Applications
[5] Minas Gjoka, Maciej Kurant, Athina Markopoulou, Carter T. Butts, Walking in Facebook: A Case Study of Unbiased Sampling of OSNs
[6] Y. Ahn, S. Han, H. Kwak, S. Moon, and H. Jeong, “Analysis of Topological Characteristics of Huge Online Social Networking Services,” in Proc. of WWW, 2007.
[7] A. Mislove, M. Marcon, K. P. Gummadi, P. Druschel, and S. Bhattacharjee,“Measurement and Analysis of Online Social Networks,” in Proc. of IMC, 2007.
[8] A. Mislove, H. S. Koppula, K. P. Gummadi, P. Druschel, and B. Bhattacharjee,“Growth of the flickr social network,” in WOSN, 2008.
[9] C. Wilson, B. Boe, A. Sala, K. P. Puttaswamy, and B. Y. Zhao, “User interactions in social networks and their implications,” in Proc. Of EuroSys, 2009.
[10] Granovetter, M. (1995) Getting a Job: A Study of Contacts and Careers (Chicago Univ. Press, Chicago), 2nd Ed.
[11] Topa, G. (2001) Rev. Econ. Studies 68, 261–295.
[12] Coleman, J. S. (1988) Am. J. Sociol. 94, S95–S120.
[13] Putnam, R. (1993) Making Democracy Work (Princeton Univ. Press, Princeton).