Sep 2009, Volume 3 Issue 3
    

  • Select all
  • Research articles
    Challenges and possible approaches: towards the petaflops computers
    Depei QIAN , Danfeng ZHU
    2009, 3(3): 273-289. https://doi.org/10.1007/s11704-009-0022-6
    Download PDF
    In parallel with the R&D efforts in USA and Europe, China’s National High-tech R&D program has setup its goal in developing petaflops computers. Researchers and engineers world-wide are looking for appropriate methods and technologies to achieve the petaflops computer system. Based on discussion on important design issues in developing the petaflops computer, this paper raises the major technological challenges including the memory wall, low power system design, interconnects, and programming support, etc. Current efforts in addressing some of these challenges and in pursuing possible solutions for developing the petaflops systems are presented. Several existing systems are briefly introduced as examples, including Roadrunner, Cray XT5 jaguar, Dawning 5000A/6000, and Lenovo DeepComp 7000. Architectures proposed by Chinese researchers for implementing the petaflops computer are also introduced. Advantages of the architecture as well as the difficulties in its implementation are discussed. Finally, future research direction in development of high productivity computing systems is discussed.
  • Research articles
    Four styles of parallel and net programming
    Zhiwei XU , Li ZHA , Yongqiang HE , Wei LIN ,
    2009, 3(3): 290-301. https://doi.org/10.1007/s11704-009-0028-0
    Download PDF
    This paper reviews the programming landscape for parallel and network computing systems, focusing on four styles of concurrent programming models, and example languages/libraries. The four styles correspond to four scales of the targeted systems. At the smallest coprocessor scale, Single Instruction Multiple Thread (SIMT) and Compute Unified Device Architecture (CUDA) are considered. Transactional memory is discussed at the multicore or process scale. The MapReduce style is examined at the datacenter scale. At the Internet scale, Grid Service Markup Language (GSML) is reviewed, which intends to integrate resources distributed across multiple datacenters. The four styles are concerned with and emphasize different issues, which are needed by systems at different scales. This paper discusses issues related to efficiency, ease of use, and expressiveness.
  • Research articles
    Cluster based parallel database management system for data intensive computing
    Jianzhong LI , Wei ZHANG ,
    2009, 3(3): 302-314. https://doi.org/10.1007/s11704-009-0031-5
    Download PDF
    This paper describes a computer-cluster based parallel database management system (DBMS), InfiniteDB, developed by the authors. InfiniteDB aims at efficiently support data intensive computing in response to the rapid growing in database size and the need of high performance analyzing of massive databases. It can be efficiently executed in the computing system composed by thousands of computers such as cloud computing system. It supports the parallelisms of intra-query, inter-query, intra-operation, inter-operation and pipelining. It provides effective strategies for managing massive databases including the multiple data declustering methods, the declustering-aware algorithms for relational operations and other database operations, and the adaptive query optimization method. It also provides the functions of parallel data warehousing and data mining, the coordinatorwrapper mechanism to support the integration of heterogeneous information resources on the Internet, and the fault tolerant and resilient infrastructures. It has been used in many applications and has proved quite effective for data intensive computing.
  • Research articles
    Minimizing interconnect length on reconfigurable meshes
    Jigang WU , Thambipillai SRIKANTHAN , Kai WANG ,
    2009, 3(3): 315-321. https://doi.org/10.1007/s11704-009-0032-4
    Download PDF
    Shorter total interconnect and fewer switches in a processor array definitely lead to less capacitance, power dissipation and dynamic communication cost between the processing elements. This paper presents an algorithm to find a maximum logical array (MLA) that has shorter interconnect and fewer switches in a reconfigurable VLSI array with hard/soft faults. The proposed algorithm initially generates the middle ([k/2]th) logical column and then makes it nearly straight for the MLA with k logical columns. A dynamic programming approach is presented to compact other logical columns toward the middle logical column, resulting in a tightly-coupled MLA. In addition, the lower bound of the interconnect length of the MLA is proposed. Experimental results show that the resultant logical array is nearly optimal for the host array with large fault size, according to the proposed lower bound.
  • Research articles
    Complex networks and computing
    Shuigeng ZHOU , Zhongzhi ZHANG ,
    2009, 3(3): 322-323. https://doi.org/10.1007/s11704-009-0047-x
    Download PDF
  • Research articles
    An alternative approach to characterize the topology of complex networks and its application in epidemic spreading
    Zonghua LIU , Xiaoyan WU , Pak-Ming HUI ,
    2009, 3(3): 324-334. https://doi.org/10.1007/s11704-009-0058-7
    Download PDF
    Based on the mean-field approach, epidemic spreading has been well studied. However, the mean-field approach cannot show the detailed contagion process, which is important in the control of epidemic. To fill this gap, we present a novel approach to study how the topological structure of complex network influences the concrete process of epidemic spreading. After transforming the network structure into hierarchical layers, we introduce a set of new parameters, i.e., the average fractions of degree for outgoing, ingoing, and remaining in the same layer, to describe the infection process. We find that this set of parameters are closely related to the degree distribution and the clustering coefficient but are more convenient than them in describing the process of epidemic spreading. Moreover, we find that the networks with exponential distribution have slower spreading speed than the networks with power-law degree distribution. Numerical simulations have confirmed the theoretical predictions.
  • Research articles
    Multidimensional views on mobile call network
    Shengqi YANG , Bin WU , Bai WANG ,
    2009, 3(3): 335-346. https://doi.org/10.1007/s11704-009-0056-9
    Download PDF
    Recent studies on social network have spurred significant interests in human behaviors. Nowadays, various kinds of interpersonal human interactions, from mobile calls to emails, provide particular avenues to explore the inherent properties of communication patterns. In this article, we present a comprehensive study on a massive anonymous call records obtained from a major mobile service operator. The important difference laid in our work and previous mainly topological analyses is that we report on multiple aspects of the dataset. By investigating the calls of the users, we find out that most calls tend to last within one minute. Call duration between two females is much longer than that of two males. But calls of males generally involve more stations than that of female, indicating a larger mobile range of the males. We also observed that people tend to communicate more with each other when they share similar characters. Besides, the network is well-connected and robust to random attack. We also demonstrate that the close-knit sub-groups with little discrepancy in the characteristics of its involved users usually evoke more calls. Another interesting discovery is that call behaviors among people between workdays and weekends is obviously distinct. Generally speaking, the goal that we research on call network through multidimensional analyses is to uncover the intricate patterns of human communications and put up reasonable insights into future service intelligence.
  • Research articles
    Correlation in mobile call networks from structure perspective
    Bin WU , Deyong HU , Qi YE , Bai WANG ,
    2009, 3(3): 347-355. https://doi.org/10.1007/s11704-009-0043-1
    Download PDF
    Researchers have done considerable work on the structure of social network recently, but mostly neglected the correlation between two connected nodes. In this paper, our primary goal is to acquire users’ structural properties in mobile call networks. We take a novel perspective—structure correlation between two connected users perspective to study the structural properties. To investigate the structural properties in static and dynamic mobile call networks, we define some metrics which are based on the clique size vectors of mobile call users. By exploring several realworldmobile call networks, which contain hundreds of thousands of mobile call users respectively, we find that people tend to communicate with the one who has a similar structure in static mobile call networks. Moreover, It is found that the connected people have similar structural changes on the whole in dynamicmobile call networks, and the structures of some two connected persons both have growing or shrinking trends. We use a visualization toolkit to give a view of the growing or shrinking scenarios temporally.
  • Research articles
    A new centrality measure based on sub-tree
    Lili RONG , Tianzhu GUO , Jiyong ZHANG ,
    2009, 3(3): 356-360. https://doi.org/10.1007/s11704-009-0046-y
    Download PDF
    How to evaluate the importance of nodes in networks and detect the centrality has become a vital problem in improving the efficiency of telecommunication and making a disease immunity strategy. We consider the mechanisms of real networks, and define a cost function to describe different hierarchies of networks to measure node importance. This method takes up a node’s regional influence as well as its global influence to evaluate its importance. The results of simulation prove that this method is proper to describe effectively and detect node discrepancies in a network.
  • Research articles
    SIS model of epidemic spreading on dynamical networks with community
    Chengyi XIA , Shiwen SUN , Feng RAO , Junqing SUN , Jinsong WANG , Zengqiang CHEN ,
    2009, 3(3): 361-365. https://doi.org/10.1007/s11704-009-0057-8
    Download PDF
    We present a new epidemic Susceptible-Infected-Susceptible (SIS) model to investigate the spreading behavior on networks with dynamical topology and community structure. Individuals in themodel are mobile agentswho are allowed to perform the inter-community (i.e., long-range) motion with the probability p. The mean-field theory is utilized to derive the critical threshold (λC) of epidemic spreading inside separate communities and the influence of the long-range motion on the epidemic spreading. The results indicate that λC is only related with the population density within the community, and the long-range motion will make the original disease-free community become the endemic state. Large-scale numerical simulations also demonstrate the theoretical approximations based on our new epidemic model. The current model and analysis will help us to further understand the propagation behavior of real epidemics taking place on social networks.
  • Research articles
    Detecting community structure in networks by representative energy
    Ji LIU , Guishi DENG ,
    2009, 3(3): 366-372. https://doi.org/10.1007/s11704-009-0042-2
    Download PDF
    Network community has attractedmuch attention recently, but the accuracy and efficiency in finding a community structure is limited by the lower resolution of modularity. This paper presents a new method of detecting community based on representative energy. The method can divide the communities and find the representative of community simultaneously. The communities of network emerges during competing for the representative among nodes in network, thus we can sketch structure of the whole network. Without the optimizing by modularity, the community of network emerges with competing for representative among those nodes. To obtain the proximate relationships among nodes, we map the nodes into a spectral matrix. Then the top eigenvectors are weighted according to their contributions to find the representative node of a community. Experimental results show that the method is effective in detecting communities of networks.
  • Research articles
    Scale-free network modles with accelerating growth
    Huan LI ,
    2009, 3(3): 373-380. https://doi.org/10.1007/s11704-009-0041-3
    Download PDF
    Complex networks are everywhere. A typical example is software network. Basing on analyzing evolutive structure of the software networks, we consider accelerating growth of network as power-law growth, which can be more easily generalized to real systems than linear growth. For accelerating growth via a power law and scale-free state with preferential linking, we focus on exploring the generic property of complex networks. Generally, two scenarios are possible. In one of them, the links are undirected. In the other scenario, the links are directed. We propose two models that can predict the emergence of power-law growth and scale-free state in good agreement with these two scenarios and can simulate much more real systems than existing scale-free network models. Moreover, we use the obtained predictions to fit accelerating growth and the connectivity distribution of software networks describing scale-free structure. The combined analytical and numerical results indicate the emergence of a novel set of models that considerably enhance our ability to understand and characterize complex networks, whose applicability reaches far beyond the quoted examples.
  • Research articles
    Hybrid information retrieval policies based on cooperative cache in mobile P2P networks
    Quanqing XU , Bin CUI , Yafei DAI , Hengtao SHEN , Zaiben CHEN , Xiaofang ZHOU ,
    2009, 3(3): 381-395. https://doi.org/10.1007/s11704-009-0055-x
    Download PDF
    The concept of Peer-to-Peer (P2P) has been introduced into mobile networks, which has led to the emergence of mobile P2P networks, and originated potential applications in many fields. However,mobile P2P networks are subject to the limitations of transmission range, and highly dynamic and unpredictable network topology, giving rise to many new challenges for efficient information retrieval. In this paper, we propose an automatic and economical hybrid information retrieval approach based on cooperative cache. In this method, the region covered by a mobile P2P network is partitioned into subregions, each of which is identified by a unique ID and known to all peers. All the subregions then constitute a mobile Kademlia (MKad) network. The proposed hybrid retrieval approach aims to utilize the floodingbased and Distributed Hash Table (DHT)-based schemes in MKad for indexing and searching according to the designed utility functions. To further facilitate information retrieval, we present an effective cache update method by considering all relevant factors. At the same time, the combination of two different methods for cache update is also introduced. One of them is pull based on time stamp including two different pulls: an on-demand pull and a periodical pull, and the other is a push strategy using update records. Furthermore, we provide detailed mathematical analysis on the cache hit ratio of our approach. Simulation experiments in NS-2 showed that the proposed approach is more accurate and efficient than the existing methods.
  • Research articles
    Class structure refactoring of object-oriented softwares using community detection in dependency networks
    Weifeng PAN , Yutao MA , Jing LIU , Yeyi QIN , Bing LI ,
    2009, 3(3): 396-404. https://doi.org/10.1007/s11704-009-0054-y
    Download PDF
    The quality of a software system is largely determined by its internal structures which always degrade over the software evolution. Therefore, the structures have to be reconditioned from time to time. However, the existing methods are very complex and resource-consuming when doing this task. In this paper, we present an approach to recondition the class structures of object-oriented (OO) software systems. It uses attribute-method networks and method-method networks to represent attributes, methods and dependencies between them; It proposes a guided community detection algorithm to obtain the optimized community structures in the method-method networks, which also correspond to the optimized class structures; It also provides a list of refactorings by comparing the optimized class structures with the real class structure in software systems and inspecting the attribute-method networks. The approach is evaluated using the open-source case study, JHotDraw 5.1, and the advantages of our approach are illustrated in comparison with existing methods.
  • Research articles
    A fast iterative-clique percolation method for identifying functional modules in protein intreaction networks
    Penggang SUN , Lin GAO ,
    2009, 3(3): 405-411. https://doi.org/10.1007/s11704-009-0048-9
    Download PDF
    Accumulating evidence suggests that biological systems are composed of interacting, separable, functional modules—groups of vertices within which connections are dense but between which they are sparse. Identifying these modules is likely through capturing the biologically meaningful interactions. In recent years, many algorithms have been developed for detecting such structures. These algorithms, however, are computationally demanding, which limits their applications. In this paper, we propose a fast iterative-clique percolation method (ICPM) for identifying overlapping functional modules in protein-protein interaction (PPI) networks. Our method is based on clique percolation method (CPM), and it not only considers the degree of nodes to minimize the search space (the vertices in k-cliques must have the degree of k
  • Research articles
    Evaluation of subgraph searching algorithms for detecting network motifs in biological networks
    Jialu HU , Lin GAO , Guimin QIN ,
    2009, 3(3): 412-416. https://doi.org/10.1007/s11704-009-0045-z
    Download PDF
    Despite several algorithms for searching subgraphs in motif detection presented in the literature, no effort has been done for characterizing their performance till now. This paper presents a methodology to evaluate the performance of three algorithms: edge sampling algorithm (ESA), enumerate subgraphs (ESU) and randomly enumerate subgraphs (RAND-ESU). A series of experiments are performed to test sampling speed and sampling quality. The results show that RAND-ESU is more efficient and has less computational cost than other algorithms for large-size motif detection, and ESU has its own advantage in small-size motif detection.
  • Research articles
    Improved collaborative filtering algorithm based on heat conduction
    Qiang GUO , Jianguo LIU , Binghong WANG ,
    2009, 3(3): 417-420. https://doi.org/10.1007/s11704-009-0050-2
    Download PDF
    In this paper, we present an improved collaborative filtering (ICF) algorithm by using the heat diffusion process to generate the user correlation. This algorithm has remarkably higher accuracy than the standard collaborative filtering (CF) using Pearson correlation. Furthermore, we introduce a free parameter β to regulate the contributions of objects to user correlation. The numerical simulation results indicate that decreasing the influence of popular objects can further improve the algorithmic accuracy and diversity.
  • Research articles
    Genealized collaboration networks in software systems: a case study of Linux kernels
    Shiwen SUN , Chengyi XIA , Junqing SUN , Zhenhai CHEN , Zengqiang CHEN ,
    2009, 3(3): 421-426. https://doi.org/10.1007/s11704-009-0053-Z
    Download PDF
    The collaboration relationships between header files in the source code of Linux kernels are analyzed by constructing a weighted Header File Collaboration Network (HFCN): each node represents a header file; two nodes are connected if corresponding header files are both included in the same source file at least once; also the link weight is assigned to evaluate the intensity of co-inclusion of two header files. Through using appropriate non-weighted and weighted quantities, structural properties of two kinds of HFCN networks(HFCN-I and HFCN-II) are characterized and analyzed. The study of Linux kernels from the viewpoint of complex networks can provide a better description of the organizational principles and evolving mechanism of complex software systems.
  • Research articles
    SWER:small world-based efficient routing for wireless sensor networks with mobile sinks
    Xuejun LIU , Jihong GUAN , Guangwei BAI , Haiming LU ,
    2009, 3(3): 427-434. https://doi.org/10.1007/s11704-009-0052-0
    Download PDF
    The interest in small-world network has highlighted the applicability of both the graph theory and the scaling theory to the analysis of network systems. In this paper, we introduce a new routing protocol, small world-based efficient routing (SWER), dedicated to supporting sink mobility and small transfers. The method is based on the concept of the small worlds where the addition of a small number of long-range links in highly clustered networks results in significant reduction in the average path length. Based on the characteristic of sensor networks, a cluster-based small world network is presented, and an analytical model is developed to analyze the expected path length. SWER adopts a simple and effective routing strategy to forward data to the mobile sink in a small transfer scene and avoid expensive mechanisms to construct a high quality route. We also study the routing scheme and analyze the expected path length in the case where every node is aware of the existence of p longrange links. In addition, we develop a hierarchical mechanism in which the mobile sink only transmits its location information to the cluster heads when it enters a new cluster. Thus we also avoid expensive cost to flood the location of the mobile sink to the whole network.