基于复杂网络的非正式团体知识交互网络分析

针对知识在非正式团体中的传播特征,结合复杂网络理论,为了企业知识不断创新,提出了一种非正式团体知识交互网络模型.通过仿真得出,在小世界网络模型下知识的传播速度和平均知识水平比其他网络模型有明显优势,进而在非正式团体知识交互网络的描述与分析中提出利用"小世界"的平均路径长度和聚类系数来表征IFG知识交互网络中的交互频繁度和交互聚集度的思想,为进一步研究IFG组织及管理与其内部知识创新的内在联系提供了数量分析基础.     

K(Knowledge)-net: building up and its dynamics

The essence of intelligence is to use certain abilities to obtain knowledge, to use that knowledge, and to operate with that knowledge. New knowledge learned by a human is often related to old existing knowledge, and sometimes we could have more conceptual knowledge based on old knowledge. So, the knowledge in the brain exists in a related structural form, and this structure is dynamic, and therefore is evolvable. Based on the understanding of the real process of learning by a human being, we discuss how to make a model to describe the dynamic structure of knowledge. This model is also a principle of artificial brain design. Most of the knowledge a child learns is from natural language and perception information, and we define this as semantic knowledge. The model to describe the process and structure of knowledge growing in a network form is called a K-net. It is a dynamic network with two main dynamics: one is new knowledge added, and the other is aggregating knowledge existing in the network with some probability. Under these very natural conditions, we found that the network is originally a simple random net, and then some characteristics of a complex network gradually appear when more new knowledge is added and aggregated. A more interesting phenomenon is the appearance of a random hierarchical structure. Does this mean emergence?     

Distance estimation and object location via rings of neighbors

We consider four problems on distance estimation and object location which share the common flavor of capturing global information via informative node labels: low-stretch routing schemes [48], distance labeling [25], searchable small worlds [31], and triangulation-based distance estimation [34]. Focusing on metrics of low doubling dimension, we approach these problems with a common technique called rings of neighbors, which refers to a sparse distributed data structure that underlies all our constructions. Apart from improving the previously known bounds for these problems, our contributions include extending Kleinberg’s small world model to doubling metrics, and a short proof of the main result in Chan et al. [15]. Doubling dimension is a notion of dimensionality for general metrics that has recently become a useful algorithmic concept in the theoretical computer science literature. This work was done when A. Slivkins was a graduate student at Cornell University and was supported by the Packard Fellowship of Jon Kleinberg. Preliminary version of this paper has appeared in 24th Annual ACM SIGACT-SIGOPS Symposium on Principles of Distributed Computing (PODC), 2005.     

A computational model for signaling pathways in bounded small-world networks corresponding to brain size

A computational model, the bounded composite inverse-d architecture (BCIA), was developed to characterize signaling in small-world networks with large but bounded numbers of nodes, as in human brains. The model is based upon an N-dimensional symmetrical grid with borders, with complete local connections from each node and relatively fewer long-range connections. The length of the signaling pathway generated by a greedy algorithm between two nodes exhibited polylogarithmic behavior when the grid distance between the nodes was less than m, the maximal length of a long-range connection for that network. The simulated length of signaling pathway became linear with internode distance when the grid distance between the two nodes was greater than m. The intensity of long-range connections among nodes was found to be negatively related to the simulated length of signaling pathway. For a constant grid distance between nodes, the average length of a simulated signaling pathway increased with dimension of the BCIA graph. Most strikingly, BCIA simulations of networks with large but bounded numbers (10⁹–10¹³) of nodes, approximating the number of neurons in the human brain, found that the length of simulated signaling pathway can be substantially shorter than that predicted by the best known asymptotic theoretical bound in small-world networks of infinite size.     

Could any graph be turned into a small-world?

In addition to statistical graph properties (diameter, degree, clustering, etc.), Kleinberg [The small-world phenomenon: an algorithmic perspective, in: Proc. 32nd ACM Symp. on Theory of Computing (STOC), 2000, pp. 163–170] showed that a small-world can also be seen as a graph in which the routing task can be efficiently and easily done in spite of a lack of global knowledge. More precisely, in a lattice network augmented by extra random edges (but not chosen uniformly), a short path of polylogarithmic expected length can be found using a greedy algorithm with a local knowledge of the nodes. We call such a graph a navigable small-world since short paths exist and can be followed with partial knowledge of the network. In this paper, we show that a wide class of graphs can be augmented into navigable small-worlds.     

Analyzing power-thermal-performance trade-offs in a high-performance 3D NoC architecture

The emergence of three-dimensional (3D) network-on-chip (NoC) has revolutionized the design of high-performance and energy efficient manycore chips. However, in general, 3D NoC architectures still suffer from high power density and the resultant thermal hotspots leading to functionality and reliability concerns over time. The power consumption and thermal profiles of 3D NoCs can be improved by incorporating a Voltage Frequency Island (VFI)-based power management strategy and Reciprocal Design Symmetry (RDS)-based floor planning. In this paper, we undertake a detailed design space exploration for 3D NoC by considering power-thermal-performance (PTP) trade-offs. We specifically consider a small-world network-enabled 3D NoC (3D SWNoC) in this performance evaluation due to its superior performance and energy-efficiency compared to any other existing 3D NoC architectures. We demonstrate that the VFI-enabled 3D SWNoC lowers the energy-delay-product (EDP) by 57.3% on an average compared to a 2D MESH without VFI. Moreover, by incorporating VFI, we reduce the maximum temperature of 3D SWNoC by 15.2% on an average compared to the non-VFI counterpart. By complementing the VFI-based power management with RDS-based floor planning, the 3D SWNoC reduces the maximum temperature by 25.1% on an average compared to the non-VFI counterpart.     

小世界网络在多机器人编队中的应用

研究小世界网络在多机器人编队中的应用。根据小世界网络的特点,只需改变很少的几个连接,就可以很明显地改变多机器人编队的性能。分析小世界网络与多机器人编队的特点,并以Matlab7.0作为仿真软件,仿真多机器人编队通讯网络的全局效率和局部效率。仿真结果表明,小世界网络具有较高的效率和传播速度。     

一种具有动态拓扑结构的粒子群算法研究

受小世界网络模型的启发,提出了一种具有动态拓扑结构的新颖粒子群算法。该算法通过对每个粒子邻域的记忆和更新,模拟小世界网络模型中的信息传播方式。在大量基准问题上的实验结果显示,提出的算法能有效保持优秀粒子与非优粒子所占比例的均衡性,维持了种群的多样性,避免了经典粒子群算法在高维、多峰问题上的早熟收敛现象。     

基于复杂网络面向对象集成测试的研究

软件测试是保证软件质量的重要手段.面向对象的方法给软件系统带来好处的同时,也为测试带来了挑战,传统的测试方法无法应用于许多面向对象的特性.研究表明,大型软件系统内部结构具有小世界效应(Small-World,SW)和无标度特性(Scale-Free,SF).基于软件的复杂网络特性对面向对象的集成测试进行了研究,提出了一种通过分析类之间的交互复杂性和聚集复杂性来确定软件测试顺序的方法.利用该方法进行面向对象集成测试可以减少桩模块的数量,提高测试效率,且不降低原有测试覆盖度.