Computing All Pairs Shortest Paths on Sparse Graphs with Articulation Points

In most network analysis tools the computation of the shortest paths between all pairs of nodes is a fundamental step to the discovery of other properties. Among other properties is the computation of closeness centrality, a measure of the nodes that shows how central a vertex is on a given network. In this paper, the authors present a method to compute the All Pairs Shortest Paths on graphs that present two characteristics： abundance of nodes with degree value one, and existence of articulation points along the graph. These characteristics are present in many real life networks especially in networks that show a power law degree distribution as is the case of biological networks. The authors＇ method compacts the single nodes to their source, and then by using the network articulation points it disconnects the network and computes the shortest paths in the biconnected components. At the final step the authors proposed methods merges the results to provide the whole network shortest paths. The authors＇ method achieves remarkable speedup compared to state of the art methods to compute the shortest paths, as much as 7 fold speed up in artificial graphs and 3.25 fold speed up in real application graphs. The authors＇ performance improvement is unlike previous research as it does not involve elaborated setups since the authors algorithm can process significant instances on a popular workstation.

技术创新二元网络组织的理论与经验研究——基于探索与利用跨期耦合的视角

持续的组织绩效根源于短期绩效和长期适应性之间的平衡,从而根源于探索与利用之间的协同。本文首先运用理论并借助于数理模型,分析了探索与利用跨期耦合支持持续组织绩效的机理。然后,以实现探索与利用跨期耦合为视角,将网络结构分为紧密性和稀疏性两种类型,运用理论模型分析表明,紧密网络促进利用性创新却抑制探索性创新,而稀疏网络促进探索性创新却抑制利用性创新。在此基础上,结合国际典型企业实践提出了实现紧密性与稀疏性耦合的静态式和演化式二元网络结构,并分析了二元网络通过支持技术演进、市场演进和组织演进而实现探索与利用跨期耦合的机理。以丰田汽车全球复合型二元网络成功实践为例,示范和验证了二元网络的形成机制、结构特征及耦合机制。最后总结全文得出的实践启示是,为了基于网络实现组织绩效持续发展,主导企业应首先建立高层管理团队的悖论认知框架,进而基于经济和社会双重准则建立二元的经营战略、系统结构及过程,以及与之相平衡的适应性的领导力及组织文化能力发展战略。