基于Centrality的Cluster發(fā)現(xiàn)算法設(shè)計(jì)與實(shí)現(xiàn)
2萬(wàn)字 46頁(yè)
包括開(kāi)題報(bào)告和任務(wù)書(shū)，程序代碼



摘 要
現(xiàn)實(shí)世界中的許多復(fù)雜系統(tǒng)都可以使用網(wǎng)絡(luò)模型進(jìn)行描述。復(fù)雜網(wǎng)絡(luò)的結(jié)構(gòu)和性質(zhì)研究已經(jīng)成為引人注目的領(lǐng)域。對(duì)復(fù)雜網(wǎng)絡(luò)進(jìn)行中心化，發(fā)現(xiàn)復(fù)雜網(wǎng)絡(luò)中的重要節(jié)點(diǎn)，具有重要的應(yīng)用價(jià)值。
軟件系統(tǒng)其實(shí)也是一類非常重要的復(fù)雜網(wǎng)絡(luò)，不過(guò)目前為止對(duì)這方面的研究非常少見(jiàn)。軟件一般由許多相互關(guān)聯(lián)的單元和子系統(tǒng)（如子程序，類，源程序文件，庫(kù)文件等）以及這些組成元素間的交互和協(xié)作關(guān)系組成。軟件的組成元素可以看成復(fù)雜網(wǎng)絡(luò)中的節(jié)點(diǎn)，而他們之間的相互調(diào)用或是消息通信關(guān)系可以看成復(fù)雜網(wǎng)絡(luò)中的邊。目前，軟件系統(tǒng)規(guī)模日趨龐大，系統(tǒng)間的協(xié)作日趨緊密，特別是開(kāi)源軟件的發(fā)展更促進(jìn)這一趨勢(shì)。將復(fù)雜的大型軟件系統(tǒng)分解成相對(duì)獨(dú)立的軟件集群，具有重要的研究意義。
本課題運(yùn)用復(fù)雜網(wǎng)絡(luò)中心化（Centrality）思想和集群（Cluster）分析思想，針對(duì)軟件系統(tǒng)這類復(fù)雜網(wǎng)絡(luò)，設(shè)計(jì)并實(shí)現(xiàn)了一種通過(guò)計(jì)算各邊的介數(shù)指標(biāo)值找到核心節(jié)點(diǎn)，然后移除指標(biāo)值大的節(jié)點(diǎn)邊從而發(fā)現(xiàn)軟件系統(tǒng)代碼集群的算法，達(dá)到分解大型軟件系統(tǒng)的目的，將復(fù)雜問(wèn)題簡(jiǎn)單化。
本論文詳細(xì)闡述了算法的設(shè)計(jì)與實(shí)現(xiàn)過(guò)程，簡(jiǎn)述了設(shè)計(jì)本算法所依賴的理論基礎(chǔ)，包括復(fù)雜網(wǎng)絡(luò)、復(fù)雜網(wǎng)絡(luò)中心化、集群分析、軟件系統(tǒng)等；著重介紹了在實(shí)現(xiàn)過(guò)程中，計(jì)算最短路徑使用的弗洛伊德算法，判斷回路的深度優(yōu)先遍歷算法，C#圖形編程等。

關(guān)鍵詞：復(fù)雜網(wǎng)絡(luò)，中心化，軟件系統(tǒng)，集群分析

The Design and Realization of Cluster Detection Algorithm
Based On Centrality
Abstract

Most complex systems in nature can be described by models of networks, exploring the structure and property of complex networks has become one of hot topics in science. Centralization of complex networks, which can help us find important nodes in complex networks, is of great practical value in many applications.
Software systems represent another important class of complex networks, which to date have received relatively little attention in this field. Software is built up out of many interacting units and subsystems at many levels of granularity (subroutines, classes, source files, libraries, etc.), and the interactions and collaborations of those pieces can be used to define networks or graphs that form a skeletal description of a system. Nowadays, the scale of software systems and the collaboration among software systems tend to be more huge and closer. What’s more, the development of open source software makes this trend badly. Then it is significantly useful to decompose the software system into smaller independent software clusters.
Aimed at the software systems, according to the centralization of complex networks and cluster analysis principles，this research have been able to design and implement an algorithm that through finding and removing the key edges whose centrality value are the maximal to detecting the software clusters, which simplify the complex software networks.
This paper detailedly discusses the design and development progress of this algorithm; simply talks about the theory the algorithm based on, including complex networks, centralization, cluster analysis, software systems, etc; mainly introduces the Floyd algorithm counting all the shortest path of all the nodes, the DFS algorithm judging the connectivity of graphic and the C# graphic programming, etc.
Key Words：Complex networks, Centralization, Software systems, Cluster analysis.
目 錄
1. 緒論 1
1.1 課題背景及來(lái)源 1
1.2 課題研究的意義 1
1.3 論文組織結(jié)構(gòu) 2
2. 基本理論知識(shí)及其應(yīng)用 3
2.1 復(fù)雜網(wǎng)絡(luò) 3
2.1.1 概念 3
2.1.2 度量參數(shù) 6
2.1.3 研究意義 7
2.2 復(fù)雜網(wǎng)絡(luò)中心化 10
2.2.1 度指標(biāo) 11
2.2.2 緊密度指標(biāo) 12
2.2.3 特征向量指標(biāo) 13
2.2.4 介數(shù)指標(biāo) 14
2.2.5 流介數(shù)指標(biāo) 15
2.3 軟件系統(tǒng)網(wǎng)絡(luò)化特征 16
2.4 集群分析 18
3. 算法設(shè)計(jì) 20
3.1 算法設(shè)計(jì)分析 20
3.1.1 軟件系統(tǒng)拓?fù)鋱D 20
3.1.2 交通網(wǎng)絡(luò)的中心化 21
3.2 算法思想 22
4. 算法實(shí)現(xiàn) 24
4.1 開(kāi)發(fā)環(huán)境及工具 24
4.2 算法實(shí)現(xiàn) 24
4.2.1 用戶輸入界面實(shí)現(xiàn) 24
4.2.2 節(jié)點(diǎn)圖形表示 25
4.2.3 計(jì)算最短路徑 26
4.2.4 計(jì)算Centrality值 27
4.2.5 發(fā)現(xiàn)Cluster 28
4.3 結(jié)果分析 28
4.3.1 開(kāi)發(fā)難點(diǎn)及相關(guān)策略 28
4.3.2 工作展望及見(jiàn)解 29
4.3.3 創(chuàng)新思想 29
5. 總結(jié) 31
致謝 32
參考文獻(xiàn) 33
附錄 35


參考文獻(xiàn)
[1] 韓明暢,李德毅,劉常昱,李華. 軟件中的網(wǎng)絡(luò)化特征及其對(duì)軟件質(zhì)量的貢獻(xiàn)[J]. 計(jì)算機(jī)工程與應(yīng)用，2006,42(20)：29-31，186.
[2] 吳彤. 復(fù)雜網(wǎng)絡(luò)研究及其意義[J]. 哲學(xué)研究，2004,8：58-63.
[3] Watts，D.J. & Strogatz，S.H.. Collective dynamics of “small—world” networks. Nature，1998，393．
[4] Strogatz S.H.. Exploring complex networks，Nature，2001，410.
[5] Barabasi,A-L & Albeat. Emergence of scaling in random networks. Science，1999，286．
[6] 吳金閃,狄增如等. 從統(tǒng)計(jì)物理學(xué)看復(fù)雜網(wǎng)絡(luò)研究[J]. 物理學(xué)進(jìn)展，2004,24(1)：18-46.
[7] 方錦清,汪小帆,劉曾榮等. 略論復(fù)雜性問(wèn)題和非線性復(fù)雜網(wǎng)絡(luò)系統(tǒng)的研究[J]. 科技導(dǎo)報(bào)（北京）



附錄
部分核心源代碼
1. Path.cs類文件：
using System;
using System.Collections.Generic;
using System.Text;

namespace Centrality
{
class Path
{
int _value;
List _roadList;

public Path(int value, List roadList)
{
_value = value;
_roadList = roadList;
......