Comparison among Classical,Probabilistic and Quantum Algorithms for Hamiltonian Cycle Problem

The Hamiltonian cycle problem(HCP),which is an NP-complete problem,consists of having a graph G with n nodes and m edges and finding the path that connects each node exactly once.In this paper we compare some algorithms to solve a Hamiltonian cycle problem,using different models of computations and especially the probabilistic and quantum ones.Starting from the classical probabilistic approach of random walks,we take a step to the quantum direction by involving an ad hoc designed Quantum Turing Machine(QTM),which can be a useful conceptual project tool for quantum algorithms.Introducing several constraints to the graphs,our analysis leads to not-exponential speedup improvements to the best-known algorithms.In particular,the results are based on bounded degree graphs(graphs with nodes having a maximum number of edges)and graphs with the right limited number of nodes and edges to allow them to outperform the other algorithms.

Resource pre-allocation algorithms for low-energy task scheduling of cloud computing

In order to lower the power consumption and improve the coefficient of resource utilization of current cloud computing systems, this paper proposes two resource pre-allocation algorithms based on the ＂shut down the redundant, turn on the demanded＂ strategy here. Firstly, a green cloud computing model is presented, abstracting the task scheduling problem to the virtual machine deployment issue with the virtualization technology. Secondly, the future workloads of system need to be predicted： a cubic exponential smoothing algorithm based on the conservative control（CESCC） strategy is proposed, combining with the current state and resource distribution of system, in order to calculate the demand of resources for the next period of task requests. Then, a multi-objective constrained optimization model of power consumption and a low-energy resource allocation algorithm based on probabilistic matching（RA-PM） are proposed. In order to reduce the power consumption further, the resource allocation algorithm based on the improved simulated annealing（RA-ISA） is designed with the improved simulated annealing algorithm. Experimental results show that the prediction and conservative control strategy make resource pre-allocation catch up with demands, and improve the efficiency of real-time response and the stability of the system. Both RA-PM and RA-ISA can activate fewer hosts, achieve better load balance among the set of high applicable hosts, maximize the utilization of resources, and greatly reduce the power consumption of cloud computing systems.

Group Similarity and Social Influence Analysis in Online Communities

A fundamental open question in the analysis of social networks was to understand the evolution between similarity and group social ties.In general,two groups are similar for two distinct reasons:first,they grow to change their behaviors to the same group due to social influence;second,they tend to merge a group due to similar behaviors,where a process often is termed selection by sociologists.It was important to understand why two groups could merge and what led to high similarities for members in a group,influence or selection.In this paper,the techniques for identifying and modeling interactions between social influence and selection for different groups were developed.Different similarities were computed in three phases where groups came into being,before or after according to the number of common edits in Wikipedia.Experimental results showed selection played a more important role in two group merging.

Nondeterministic Probabilistic Petri Net -- A New Method to Study Qualitative and Quantitative Behaviors of System

There are many variants of Petri net at present, and some of them can be used to model system with both function and performance specification, such as stochastic Petri net, generalized stochastic Petri net and probabilistic Petri net. In this paper, we utilize extended Petri net to address the issue of modeling and verifying system with probability and nondeterminism besides function aspects. Using probabilistic Petri net as reference, we propose a new mixed model NPPN （Nondeterministic Probabilistic Petri Net） system, which can model and verify systems with qualitative and quantitative behaviours. Then we develop a kind of process algebra for NPPN system to interpret its algebraic semantics, and an action- based PCTL （Probabilistic Computation Tree Logic） to interpret its logical semantics. Afterwards we present the rules for compositional operation of NPPN system based on NPPN system process algebra, and the model checking algorithm based on the action-based PCTL. In order to put the NPPN system into practice, we develop a friendly and visual tool for modeling, analyzing, simulating, and verifying NPPN system using action-based PCTL. The usefulness and effectiveness of the NPPN system are illustrated by modeling and model checking an elaborate model of travel arrangements workflow.

Spintronics intelligent devices

Intelligent computing paradigms have become increasingly important for the efficient processing of massive amounts of data.However,using traditional electronic devices to implement these intelligent paradigms is currently mismatched and limited by their energy,area,and speed.Spintronics,which exploits the magnetic and electrical properties of electrons,could break through these limitations and bring new possibilities to electrical devices.In particular,the tunneling magnetoresistance effect,merging quantum and spintronics,enables spintronic devices to be compatible with standard integrated circuits with a magnetic tunnel junction(MTJ)design,showing great potential for implementing hardware-based intelligent frameworks.In this review,we introduce the specific capabilities of MTJs,including nonvolatility,stochasticity,plasticity,and nonlinearity,which are highly favorable in artificial intelligence algorithms.We then present how these devices could impact the development of intelligent computing,including in-memory computing,probabilistic computing,and neuromorphic computing.Finally,we discuss their challenges and perspectives in intelligent hardware implementations.