基于Centrality的Cluster發(fā)現(xiàn)算法設計與實現(xiàn)
2萬字 46頁
包括開題報告和任務書，程序代碼



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

關鍵詞：復雜網(wǎng)絡，中心化，軟件系統(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 課題背景及來源 1
1.2 課題研究的意義 1
1.3 論文組織結構 2
2. 基本理論知識及其應用 3
2.1 復雜網(wǎng)絡 3
2.1.1 概念 3
2.1.2 度量參數(shù) 6
2.1.3 研究意義 7
2.2 復雜網(wǎng)絡中心化 10
2.2.1 度指標 11
2.2.2 緊密度指標 12
2.2.3 特征向量指標 13
2.2.4 介數(shù)指標 14
2.2.5 流介數(shù)指標 15
2.3 軟件系統(tǒng)網(wǎng)絡化特征 16
2.4 集群分析 18
3. 算法設計 20
3.1 算法設計分析 20
3.1.1 軟件系統(tǒng)拓撲圖 20
3.1.2 交通網(wǎng)絡的中心化 21
3.2 算法思想 22
4. 算法實現(xiàn) 24
4.1 開發(fā)環(huán)境及工具 24
4.2 算法實現(xiàn) 24
4.2.1 用戶輸入界面實現(xiàn) 24
4.2.2 節(jié)點圖形表示 25
4.2.3 計算最短路徑 26
4.2.4 計算Centrality值 27
4.2.5 發(fā)現(xiàn)Cluster 28
4.3 結果分析 28
4.3.1 開發(fā)難點及相關策略 28
4.3.2 工作展望及見解 29
4.3.3 創(chuàng)新思想 29
5. 總結 31
致謝 32
參考文獻 33
附錄 35


參考文獻
[1] 韓明暢,李德毅,劉常昱,李華. 軟件中的網(wǎng)絡化特征及其對軟件質量的貢獻[J]. 計算機工程與應用，2006,42(20)：29-31，186.
[2] 吳彤. 復雜網(wǎng)絡研究及其意義[J]. 哲學研究，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)計物理學看復雜網(wǎng)絡研究[J]. 物理學進展，2004,24(1)：18-46.
[7] 方錦清,汪小帆,劉曾榮等. 略論復雜性問題和非線性復雜網(wǎng)絡系統(tǒng)的研究[J]. 科技導報（北京）



附錄
部分核心源代碼
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;
......