Study of complex networks by researchers from many disciplines has provided penetrating insights on various complex systems. A study of the world wide web from a network theoretic perspective has led to the design of new search engines [65]. The spread of diseases is now better understood by analyzing the underlying social network [26]. The study of metabolic networks, protein-protein interaction networks and the transcriptional regulatory networks with graph theoretic rigor, has led to the growing importance of an interdisciplinary approach [71]. Network centrality measures, which has been of interest to the social scientists, from as long as 1950 [13], is today studied extensively in the framework of complex networks. The thesis is an investigation on understanding human navigation with a network analytic approach using the well established and widely used centrality measures. Experiments were conducted on human participants to observe how people navigate in a complex environment. We made human participants way-find a destination from a source on a complex network and analyzed the paths that were taken. Our analysis established a fact that the learning process involved in navigating better in an unknown network boils down to learning certain strategic locations on the network. The vertices in the paths taken by the participants, when analyzed using the available centrality measures, enabled us to conclude experimentally that humans are naturally inclined to learn superior ranked vertices to navigate better and reach their intended destination. Our experiments were based on a word game called the word-morph. A generalized version of the experiment was conducted on a 6x6 photo collage with an underlying network hidden from the participant. A detailed analysis of the above experiment established a fact that, when humans are asked to take a goal-directed path, they were prone to take a path that passed through landmark nodes in the network. We call such paths center-strategic. We then present an algorithm that simulates the navigational strategy adopted by humans. We show empirically that the algorithm performs better than naive random walk based navigational techniques. We observe that the algorithm produces rich center-strategic paths on scale-free networks. We note that the effectiveness of the algorithm is highly dependent on the topology of the network by comparing its functionality on Erdos-Renyi networks and Barabasi-Albert networks. Then we discuss a lookahead algorithm to compute betweenness centrality in networks under vertex deletion operations. We show that the widely used Brandes algorithm can be modified to a lookahead version. We show that our proposed algorithm performs better than recomputing the betweenness centrality values in the vertex deleted graph. We show that our method works 20% faster than the Brandes algorithm.

This diploma thesis is focusing on description of processing social network analysis, design and implementation of a model that simulates a particular social network and its analysis. Social networks are modern and very used in this time. They are very good point for exploring. This project deal with static analysis social network, where social network is constructed by graph. We nd out di erent properties of single component and than we establish signi cance of them. Relationships between components are important too for us, because they have a big influence on propagation information in network. Structural properties figure out existence of di fferent communities. We simulate social network with multi-agent systems, they are desirable for represent changes in network. Multi-agent systems have implemented a simulation model that represents a particular social network. His behaviour was analyzed and examinated by chosen methods.

在政治權力結構中，權臣與派系在其政治人物的社會網絡中扮演重要的角色。本論文研究由職官年表中探勘權臣與派系。我們提出資料探勘演算法由職官年表中探勘循序共現樣式，以探勘出政府官員官職陞貶的共現關係。接著根據所探勘出的循序共現樣式，建立官員之間的社會網絡。透過社會網絡分析中的網絡中心性與社群偵測分別探勘出權臣與派系。本論文以清康熙時期的職官年表實驗驗證。透過視覺化分析顯示本論文所提出的方法有助於歷史學者的研究。 / In a power structure, chief officials and cliques play important roles in the social network and have high influence on politics. This thesis proposes an approach of social network mining from official chronologies to discover the chief officials and the cliques. We propose and develop the algorithm to discover the sequential co-occurrence patterns from official chronologies. Then the social network is constructed based on the discovered sequential co-occurrence patterns. Chief officials are discovered by network centrality analysis while cliques are discovered by community analysis of the constructed social network. The official chronology of Kangxi Emperor is taken as an example for experiments and the visualization analysis demonstrates that the proposed methods are helpful to assist historian for historical research.

近幾年在金融風暴及全球競爭等影響下，企業紛紛導入商業智慧平台，提供管理階層可簡易且快速的分析各種可量化管理的關鍵指標。但在後續的推廣上，經常會因商業智慧系統提供的資訊過於豐富，造成使用者在學習階段無法有效的取得所需資訊，導致商業智慧無法發揮預期效果。本論文以使用者在商業智慧平台上的操作相似度進行分析，建立相對於實體部門的凝聚子群，且用中心性計算各節點的關聯加權，整合至所設計的推薦機制，用以提升商業智慧平台成功導入的機率。經模擬實驗的證實，在推薦機制中考慮此因素會較原始的推薦機制擁有更高的精確度。 / In recent years, enterprises are facing financial turmoil, global competition, and shortened business cycle. Under these influences, enterprises usually implement the Business Intelligence platform to help managers get the key indicators of business management quickly and easily. In the promotion stage of such Business Intelligence platforms, users usually give up using the system due to huge amount of information provided by the BI platform. They cannot intuitively obtain the required information in the early stage when they use the system. In this study, we analyze the similarity of users’ operations on the BI platform and try to establish cohesive subgroups in the corresponding organization. In addition, we also integrate the associated weighting factor calculated from the centrality measures into the recommendation mechanism to increase the probability of successful uses of BI platform. From our simulation experiments, we find that the recommendation accuracies are higher when we add the clustering result and the associated weighting factor into the recommendation mechanism.