摘 要

社會(huì)網(wǎng)絡(luò)是指人們根據(jù)相識(shí)關(guān)系所形成的網(wǎng)絡(luò)形態(tài)。隨著萬(wàn)維網(wǎng)的迅速發(fā)展，其中蘊(yùn)含的社會(huì)網(wǎng)絡(luò)迅速膨脹，其結(jié)構(gòu)異常復(fù)雜，導(dǎo)致人們很難通過(guò)數(shù)字、表格或文字的方式對(duì)其進(jìn)行表示、分析和管理，并使其中所包含的豐富信息資源難于被發(fā)現(xiàn)和有效利用?？梢暬椒梢詫?fù)雜的社會(huì)網(wǎng)絡(luò)結(jié)構(gòu)轉(zhuǎn)換成美觀的圖形，輔助人們直觀地理解社會(huì)網(wǎng)絡(luò)結(jié)構(gòu)并從中挖掘有用的信息，是社會(huì)網(wǎng)絡(luò)分析的一個(gè)重要途徑。在前人研究的基礎(chǔ)上，本論文針對(duì)從照片共享網(wǎng)站Flickr中采集的社會(huì)網(wǎng)絡(luò)數(shù)據(jù)，通過(guò)在SqlServer數(shù)據(jù)庫(kù)管理平臺(tái)上的SQL編程對(duì)社會(huì)網(wǎng)絡(luò)數(shù)據(jù)集進(jìn)行了壓縮，并基于Matlab平臺(tái)設(shè)計(jì)和實(shí)現(xiàn)了布點(diǎn)算法對(duì)提取的關(guān)鍵網(wǎng)絡(luò)結(jié)構(gòu)進(jìn)行了可視化展示。論文的詳細(xì)研究工作包括：
（1）通過(guò)考察Flickr網(wǎng)站，以E-R圖的方式總結(jié)了“用戶(hù)”、“圖片”、“標(biāo)簽”等數(shù)據(jù)的總體組織結(jié)構(gòu)，對(duì)選取的Flickr數(shù)據(jù)集進(jìn)行了簡(jiǎn)單說(shuō)明，并從數(shù)據(jù)壓縮方法和作圖算法兩個(gè)方面對(duì)目前社會(huì)網(wǎng)絡(luò)可視化技術(shù)的研究現(xiàn)狀進(jìn)行了總結(jié)；
（2）為了提高數(shù)據(jù)壓縮的效率，提出了使用SqlServer平臺(tái)上SQL編程的社會(huì)網(wǎng)絡(luò)數(shù)據(jù)集壓縮方案；按照方案，以給定用戶(hù)作為中心節(jié)點(diǎn)提取了周邊的局部社會(huì)網(wǎng)絡(luò)，根據(jù)局部社會(huì)網(wǎng)絡(luò)中用戶(hù)節(jié)點(diǎn)度數(shù)選取了關(guān)鍵的網(wǎng)絡(luò)節(jié)點(diǎn)，通過(guò)查找最短路徑將中心節(jié)點(diǎn)與關(guān)鍵節(jié)點(diǎn)關(guān)聯(lián)起來(lái)，最終得到了三個(gè)矩陣形式表示的關(guān)鍵社會(huì)網(wǎng)絡(luò)；
（3）鑒于Matlab平臺(tái)對(duì)向量操作和圖形化操作的良好支撐，提出了利用Matlab平臺(tái)實(shí)現(xiàn)可視化算法和繪制關(guān)鍵社會(huì)網(wǎng)絡(luò)圖的方案；按照方案，首先設(shè)計(jì)和實(shí)現(xiàn)了相關(guān)算法按照“同心圓”的模式圍繞中心節(jié)點(diǎn)對(duì)關(guān)鍵社會(huì)網(wǎng)絡(luò)進(jìn)行了初始布點(diǎn)，然后實(shí)現(xiàn)了力引導(dǎo)布點(diǎn)算法對(duì)關(guān)鍵社會(huì)網(wǎng)絡(luò)進(jìn)行了節(jié)點(diǎn)位置調(diào)節(jié)和可視化作圖，最后設(shè)計(jì)和實(shí)現(xiàn)了相關(guān)算法引入輔助節(jié)點(diǎn)對(duì)作圖結(jié)果進(jìn)行了完善，得到了較為美觀、清晰的關(guān)鍵社會(huì)網(wǎng)絡(luò)圖。


關(guān)鍵詞
復(fù)雜網(wǎng)絡(luò)，社會(huì)網(wǎng)絡(luò)，可視化，可視化算法，壓縮算法，布點(diǎn)算法
ABSTRACT

Social network is formed by people with acquaintance relationships. With the rapid grow of the World Wide Web, the social network in cyberworld expands fastly, and its structure is so complex that the traditional methods like figures, tables or text are useless to show, analysis and manage the social network, making a wealth of information resources contained hard to be discovered and used effectively. Visualization, an important way to analysis social network nowadays, can convert complex social network structure into beautiful graph, therefore help people intuitively understand social network structure and dig more useful information in it. Based on previous research efforts, this thesis mainly focuses on a social network dataset retrieved from the photo-sharing website Flickr, by extracting key network for the dataset through SQL programs on SqlServer platform, designing and implementing algorithms to layout and display the key network on Matlab platform. In detail, the research work in the thesis includes:
(1) By study the Flickr website, the overall organizational structure of data containing "user", "image" and "tag" is summed up and illustrated in an E-R diagram, the selected data set of social network in Flickr is introduced, and the current art of state of social network visualization technology is explained in two aspects of data compression methods and layout algorithms;
(2) In order to improve the efficiency of data compression, a new scheme is proposed which bases on SQL programming on SqlServer platform; according to this scheme, the local social network surrounding a given user (noted as the central node in the local network) is extracted, some key nodes with big degrees in local social network are selected, the nodes locating on the shortest path of the central nodes and key nodes are selected, and eventually three key social networks are retrieved and represented in matrix forms.
(3) Because that the Matlab platform can well support vector operations and graphics operations, a visualization scheme is proposed which uses Matlab to implement visualization algorithms and draw the key social network diagrams; according to this scheme, an algorithm is designed and implemented to initially layout nodes in the key social networks in a "concentric circles" pattern, a traditional force-directed layout algorithm is implemented to automatically adjust the positions of nodes in the key social networks and to draw the diagrams of key social networks, another algorithm is designed and implemented to import auxiliary nodes into the diagrams of key social networks to make these diagrams more beautiful and more intuitionistic.

KEYWORDS
Complex network , Social Network , Visualization , Visual algorithm , Compression algorithm , Layout algorithm
目 錄

摘 要 I
ABSTRACT II
1.1 研究背景 1
1.2 國(guó)內(nèi)外研究現(xiàn)狀 1
1.2.1 國(guó)外研究現(xiàn)狀 1
1.2.2 國(guó)內(nèi)研究現(xiàn)狀 2
1.3 研究?jī)?nèi)容、方法、手段及預(yù)期成果 2
1.3.1 研究?jī)?nèi)容 2
1.3.2 研究方法及手段 2
1.3.3 預(yù)期成果 3
1.4 章節(jié)安排 3
第二章 Flickr網(wǎng)站及可視化技術(shù)簡(jiǎn)介 4
2.1 Flickr網(wǎng)站 4
2.1.1 網(wǎng)站簡(jiǎn)介 4
2.1.2 網(wǎng)站總體結(jié)構(gòu) 5
2.1.3 數(shù)據(jù)集 6
2.2 數(shù)據(jù)壓縮技術(shù)概述 6
2.2.1 壓縮與可視化的關(guān)系 6
2.2.2 壓縮算法的概述 7
2.3 可視化作圖技術(shù)概述 8
2.3.1 作圖算法的要求 8
2.3.2 作圖算法的思想 8
2.4 小結(jié) 10
..