Personalized PageRank Clustering: A graph clustering algorithm based on random walks

Graph clustering has been an essential part in many methods and thus its accuracy has a significant effect on many applications. In addition, exponential growth of real-world graphs such as social networks, biological networks and electrical circuits demands clustering algorithms with nearly-linear time and space complexity. In this paper we propose Personalized PageRank Clustering (PPC) that employs the inherent cluster exploratory property of random walks to reveal the clusters of a given graph. We combine random walks and modularity to precisely and efficiently reveal the clusters of a graph. PPC is a top-down algorithm so it can reveal inherent clusters of a graph more accurately than other nearly-linear approaches that are mainly bottom-up. It also gives a hierarchy of clusters that is useful in many applications. PPC has a linear time and space complexity and has been superior to most of the available clustering algorithms on many datasets. Furthermore, its top-down approach makes it a flexible solution for clustering problems with different requirements.     

SaxsMDView: a three‐dimensional graphics program for displaying force vectors

A new three‐dimensional graphics program, SaxsMDView, is described. The program performs a three‐dimensional graphical representation for protein molecules along with the force vector (or vector potential) applying to each atom. The displayed object can be rotated and translated in arbitrary directions by interactive mouse manipulation. While SaxsMDView was originally intended to visualize the result of SAXS_MD, a previously developed program based on the restrained molecular dynamics with small‐angle X‐ray scattering constraints, it can also be useful for graphical representation of other objects such as coarse‐grained molecular models reconstructed by ab initio modelling or solvent site‐dipole field vectors induced around the protein molecule. Some examples of the application of the program including the graphical analyses of the results with SAXS_MD are also presented.     

A three-dimensional Markov field approach for the analysis of atomic clustering in atom probe data

Solute clustering is increasingly recognised as a significant characteristic within certain material systems that can be tailored to the optimization of bulk properties and performance. Atom probe tomography (APT) is emerging as a powerful tool for the detection of these nanoscale features; however, complementary to experiment, precise and efficient characterization algorithms are required to identify and characterise these nanoclusters within the potentially massive three-dimensional atomistic APT datasets. In this study, a new three-dimensional Markov field (3DMF) cluster identification algorithm is proposed. The algorithm is based upon an analysis of the direct atomic neighbourhood surrounding each atom, and the only input parameter required utilises known crystallographic properties of the system. Further, an array of statistical approaches has been developed and applied with respect to the results generated by the 3DMF algorithm including: an S _N statistic, a two-tailed z-test, a difference measure, the χ² test, and a direct evaluation of the Warren–Cowley parameter for short-range ordering. Finally, the methodologies have been applied to the characterization of the nanostructural evolution of an Al-1.1Cu-0.5Mg (at.%) alloy subjected to a variety of heat treatments.     

Development and exploration of a new methodology for the fitting and analysis of XAS data

A new data analysis methodology for X‐ray absorption near‐edge spectroscopy (XANES) is introduced and tested using several examples. The methodology has been implemented within the context of a new Matlab‐based program discussed in a companion related article [Delgado‐Jaime et al. (2010), J. Synchrotron Rad. 17 , 132–137]. The approach makes use of a Monte Carlo search method to seek appropriate starting points for a fit model, allowing for the generation of a large number of independent fits with minimal user‐induced bias. The applicability of this methodology is tested using various data sets on the Cl K‐edge XAS data for tetragonal CuCl₄^2?, a common reference compound used for calibration and covalency estimation in M—Cl bonds. A new background model function that effectively blends together background profiles with spectral features is an important component of the discussed methodology. The development of a robust evaluation function to fit multiple‐edge data is discussed and the implications regarding standard approaches to data analysis are discussed and explored within these examples.     

Simulation study of phase retrieval for hard X-ray in-line phase contrast imaging

X-ray phase contrast imaging (XPCI) is a novel method that exploits the phase shift for the incident X-ray to form an image. For light elements such as carbon, hydrogen and oxygen, the phase-shift term can be up to 1000 times greater than the absorption term in the hard X-ray energy region. So XPCI has attracted much attention in recent years. Various methods for XPCI have been proposed and demonstrated on synchrotron devices and other X-ray sources[1―13], particularly the in-line metho…     

分子构象聚类中的K-means密度峰值搜索算法

分子构象的聚类是搜索分子动力学模拟轨迹中代表构象的主要方法。 它是分析复杂构象改变或分子间相互作用机制的关键步骤. 作为一种基于密度的聚类算法,密度峰值搜索算法因其聚类的准确度而被应用于分子聚类过程中. 但随着模拟时长的增长,密度峰值搜索算法较低的计算效率限制了其应用的可能. 本文提出K-means密度峰值搜索算法的聚类算法,它是密度峰值搜索算法在计算效率方面的一个扩展版本,用于解决密度峰值搜索算法中巨大的资源消耗问题. 在K-means密度峰值搜索算法中,首先,通过高效的聚类算法(例如K-means)进行初始聚类,得到的聚类中心被定义为具有权重的典型点. 然后,对加权的典型点通过密度峰值搜索算法实现二次聚类,并细化点为核心点、边界点、加细光晕点. 在与密度峰值搜索算法具有相似的精度的同时,计算复杂度由O(n²)降至O(n). 通过二面角,二级结构,关联图描述的分子构象,将KFDP用于多个模拟轨迹的聚类过程中. 并通过与K-means聚类算法,DBSCAN聚类算法的比较结果,验证了K-means密度峰值搜索算法的优势.     

Design of quantum VQ iteration and quantum VQ encoding algorithm taking O（√N） steps for data compression

Vector quantization (VQ) is an important data compression method. The key of the encoding of VQ is to find the closest vector among N vectors for a feature vector. Many classical linear search algorithms take $O(N)$ steps of distance computing between two vectors. The quantum VQ iteration and corresponding quantum VQ encoding algorithm that takes $O(\sqrt N )$ steps are presented in this paper. The unitary operation of distance computing can be performed on a number of vectors simultaneously because the quantum state exists in a superposition of states. The quantum VQ iteration comprises three oracles, by contrast many quantum algorithms have only one oracle, such as Shor's factorization algorithm and Grover's algorithm. Entanglement state is generated and used, by contrast the state in Grover's algorithm is not an entanglement state. The quantum VQ iteration is a rotation over subspace, by contrast the Grover iteration is a rotation over global space. The quantum VQ iteration extends the Grover iteration to the more complex search that requires more oracles. The method of the quantum VQ iteration is universal.     

Cluster synchronization in networks of distinct groups of maps

In this paper, we study cluster synchronization in general bi-directed networks of nonidentical clusters, where all nodes in the same cluster share an identical map. Based on the transverse stability analysis, we present sufficient conditions for local cluster synchronization of networks. The conditions are composed of two factors: the common inter-cluster coupling, which ensures the existence of an invariant cluster synchronization manifold, and communication between each pair of nodes in the same cluster, which is necessary for chaos synchronization. Consequently, we propose a quantity to measure the cluster synchronizability for a network with respect to the given clusters via a function of the eigenvalues of the Laplacian corresponding to the generalized eigenspace transverse to the cluster synchronization manifold. Then, we discuss the clustering synchronous dynamics and cluster synchronizability for four artificial network models: (i) p-nearest-neighborhood graph; (ii) random clustering graph; (iii) bipartite random graph; (iv) degree-preferred growing clustering network. From these network models, we are to reveal how the intra-cluster and inter-cluster links affect the cluster synchronizability. By numerical examples, we find that for the first model, the cluster synchronizability regularly enhances with the increase of p, yet for the other three models, when the ratio of intra-cluster links and the inter-cluster links reaches certain quantity, the clustering synchronizability reaches maximal.     

Molecular many-body dissociation: Data reduction strategies in translational spectroscopy

Advanced time- and position-sensitive multi-hit detectors allow to study molecular breakup processes into two, three, and more massive fragments by translational spectroscopy. We discuss the feasibility to perform kinematically complete final state analysis of complex molecular dissociation processes using such detectors. We have developed new algorithms to determine - for an arbitrary number of fragments - the fragment momentum vectors in the center-of-mass frame from the measured positions and arrival time differences. These algorithms can easily be implemented to perform online data reduction in coincidence experiments. We have tested the new data reduction strategies in an experimental study and in Monte-Carlo simulations of realistic experimental conditions. We show that the new algorithms can discriminate between two-, three-, and four-body decay of a four-atomic molecule and can uniquely determine the momentum vectors of all fragments. For two-body decay, we find that the accuracy of the new algorithm is superior to the frequently used approximate formula introduced by DeBruijn and Los. We demonstrate this improvement in the evaluation of experimental data for the decay of laser-excited triatomic hydrogen H₃ 3s (N=1,K=0) into H + H₂(v,J) fragment pairs. Received 12 April 2000     

Parallel computing for fringe pattern processing: A multicore CPU approach in MATLAB environment

In the process of measurements such as optical interferometry and fringe projection, an important stage is fringe pattern analysis. Many advanced fringe analysis algorithms have been proposed including regularized phase tracking (RPT), partial differential equation based methods, wavelet transform, Wigner–Ville distribution, and windowed Fourier transform. However, most of those algorithms are computationally expensive. MATLAB^® is a general algorithm development environment with powerful image processing and other supporting toolboxes. It is also commonly used in photomechanical data analysis. With rapid development of multicore CPU technique, using multicore computer and MATLAB^® is an intuitive and simple way to speed up the algorithms for fringe pattern analysis. The paper introduces two acceleration approaches for fringe pattern processing. The first approach is task parallelism using multicore computer and MATLAB^® parallel computing toolbox. Since some algorithms are embarrassing problems, our first approach makes use of this characteristic to parallelize these algorithms. For this approach, parallelized windowed Fourier filtering (WFF) algorithm serves as an example to show how parallel computing toolbox accelerates the algorithm. Second, data parallelism using multicore computer and MATLAB^® parallel computing toolbox is proposed. A high level parallel wrapping structure is designed, which can be used for speeding up any local processing algorithms. WFF, windowed Fourier ridges (WFR), and median filter are used as examples to illustrate the speedup. At last, the results show that the parallel versions of former sequential algorithm with simple modifications achieve the speedup up to 6.6 times.     

A general rigorous quantum dynamics algorithm to calculate vibrational energy levels of pentaatomic molecules

An exact variational algorithm is presented for calculating vibrational energy levels of pentaatomic molecules without any dynamical approximation. The quantum mechanical Hamiltonian of the system is expressed in a set of orthogonal coordinates defined by four scattering vectors in the body-fixed frame. The eigenvalue problem is solved using a two-layer Lanczos iterative diagonalization method in a mixed grid/basis set. A direct product potential-optimized discrete variable representation (PO-DVR) basis is used for the radial coordinates while a non-direct product finite basis representation (FBR) is employed for the angular variables. The two-layer Lanczos method requires only the actions of the Hamiltonian operator on the Lanczos vectors, where the potential-vector products are accomplished via a pseudo-spectral transform technique. By using Jacobi, Radau and orthogonal satellite vectors, we have proposed 21 types of orthogonal coordinate systems so that the algorithm is capable of describing most five-atom systems with small and/or large amplitude vibrational motions. Finally, an universal program (PetroVib) has been developed. Its applications to the molecules , and the van der Waals cluster He₃Cl₂ are also discussed.     

A complex networks approach for data clustering

This work proposes a method for data clustering based on complex networks theory. A data set is represented as a network by considering different metrics to establish the connection between each pair of objects. The clusters are obtained by taking into account five community detection algorithms. The network-based clustering approach is applied in two real-world databases and two sets of artificially generated data. The obtained results suggest that the exponential of the Minkowski distance is the most suitable metric to quantify the similarities between pairs of objects. In addition, the community identification method based on the greedy optimization provides the best cluster solution. We compare the network-based clustering approach with some traditional clustering algorithms and verify that it provides the lowest classification error rate.     

基于MPI和OpenMP的三维弹性波方程混合并行有限差分算法*

三维弹性波方程有限差分模拟具有大计算量和大内存消耗的特点,在常规计算机上使用传统算法往往无法满足计算要求。该文以高性能计算机集群为平台,基于MPI和OpenMP混合编程技术,构建了一种新型三维弹性波方程并行有限差分算法。该算法基于MPI将总任务分配给多个进程,同时在每个进程中基于OpenMP将子任务分配给多个线程。各个进程具有独立的内存空间,各个线程共享所在进程的内存空间。充液井孔声场的数值模拟结果表明,与基于OpenMP的并行有限差分算法相比,基于MPI和OpenMP的混合并行有限差分算法可以利用计算机集群的多个节点进行并行计算,既极大地提高了计算速度,又有效地降低了单个节点的内存消耗。     

Combining clustering and classification for remote-sensing images using unlabeled data

A joint clustering and classification approach is proposed.This approach exploits unlabeled data for efficient clustering,which is applied in the classification with support vector machine(SVM) in the case of small-size training samples.The proposed method requires no prior information on data labels,and yields better cluster structures.Through cluster assumption and the notions of support vectors,the most confident k cluster centers and data points near the cluster boundaries are labeled and used to train a reliable SVM classifier.Our method gains better estimation of data distributions and mitigates the unrepresentative problem of small-size training samples.The data set collected from Landsat Thematic Mapper(Landsat TM-5) validates the effectiveness of the proposed approach.     

Clustering gene expression data analysis using an improved EM algorithm based on multivariate elliptical contoured mixture models

Clustering gene expression data is an important research topic in bioinformatics because knowing which genes act similarly can lead to the discovery of important biological information. Many clustering algorithms have been used in the field of gene clustering. The multivariate Gaussian mixture distribution function was frequently used as the component of the finite mixture model for clustering, however the clustering cannot be restricted to the normal distribution in the real dataset. In order to make the cluster algorithm strong adaptability, this paper proposes a new scheme for clustering gene expression data based on the multivariate elliptical contoured mixture models (MECMMs). To solve the problem of over-reliance on the initialization, we propose an improved expectation maximization (EM) algorithm by adding and deleting initial value for the classical EM algorithm, and the number of clusters can be treated as a known parameter and inferred with the QAIC criterion. The improved EM algorithm based on the MECMMs is tested and compared with some other clustering algorithms, the performance of our clustering algorithm has been extensively compared over several simulated and real gene expression datasets. Our results indicated that improved EM clustering algorithm is superior to the classical EM algorithm and the support vector machines (SVMs) algorithm, and can be widely used for gene clustering.     

遗传算法在二维电磁成像病态方程求解中的应用研究

 病态方程的计算是电磁成像中一个难以避免但又迄今未得到有效解决的难题。遗传算法以其强大的搜索寻优功能为该难题的解决提供了一种新的途径。分析了将遗传算法应用于电磁成像反演计算中的可能性和优势，并通过两个数值计算举例，一个用遗传算法计算病态线性方程组，一个用遗传算法计算TM入射波下的二维微波成像，证明遗传算法用于电磁成像中计算病态方程是可行和有效的。     

Structure and elastic properties of a nematic liquid crystal: A theoretical treatment and molecular dynamics simulation

The Frank elasticity constants which describe splay (K ₁), twist (K ₂), and bend (K ₃) distortion modes are investigated for 4-n-pentyl-4'-cyanobiphenyl (5CB) in the nematic liquid crystal. The calculations rest on statistical-mechanical approaches where the absolute values of K _i (i=1,2,3) are dependent on the direct correlation function (DCF) of the corresponding nematic state. The DCF was determined using the pair correlation function by solving the Ornstein-Zernike equation. The pair correlation function, in turn, was obtained from molecular dynamics (MD) trajectory. Three different approaches for calculations of the elasticity constants were employed based on different level of approximation about the orientational order and molecular correlations. The best agreement with experimental values of elasticity constants was obtained in a model where the full orientational distribution function was used. In addition we have investigated the approximation about spherical distribution of the intermolecular vectors in the nematic phase, often used in derivation of various mean-field theories and employed here for the construction of the DCF. We found that this assumption is not strictly valid, in particular a strong deviation from the isotropic distribution is observed for short intermolecular distances. Received 22 March 2000 and Received in final form 9 June 2000     

A Penalized Matrix Normal Mixture Model for Clustering Matrix Data

Along with advances in technology, matrix data, such as medical/industrial images, have emerged in many practical fields. These data usually have high dimensions and are not easy to cluster due to their intrinsic correlated structure among rows and columns. Most approaches convert matrix data to multi dimensional vectors and apply conventional clustering methods to them, and thus, suffer from an extreme high-dimensionality problem as well as a lack of interpretability of the correlated structure among row/column variables. Recently, a regularized model was proposed for clustering matrix-valued data by imposing a sparsity structure for the mean signal of each cluster. We extend their approach by regularizing further on the covariance to cope better with the curse of dimensionality for large size images. A penalized matrix normal mixture model with lasso-type penalty terms in both mean and covariance matrices is proposed, and then an expectation maximization algorithm is developed to estimate the parameters. The proposed method has the competence of both parsimonious modeling and reflecting the proper conditional correlation structure. The estimators are consistent, and their limiting distributions are derived. We applied the proposed method to simulated data as well as real datasets and measured its clustering performance with the clustering accuracy (ACC) and the adjusted rand index (ARI). The experiment results show that the proposed method performed better with higher ACC and ARI than those of conventional methods.     

早M型矮恒星光谱聚类方法与分析

大规模光谱巡天项目如LAMOST等产生了海量极具研究价值的观测数据,如何对此数量级的数据进行有效的分析是当前的一个研究热点。聚类算法是一类无监督的机器学习算法,可以在不依赖于领域知识的情况下对数据进行处理,发现其中的规律与结构。恒星光谱聚类是天文数据处理中一项非常重要的工作,主要对海量光谱巡天数据按照其物理及化学性质分类。针对LAMOST巡天中的早M型矮恒星的光谱数据,使用多种聚类算法如K-Means,Bisecting K-Means和OPTICS算法做了聚类分析,研究不同聚类算法在早M型恒星数据的表现。聚类算法在一定程度依赖于其使用的距离度量算法,同时研究了欧氏距离、曼哈顿距离、残差分布距离和上述三种聚类算法搭配下的表现。实验结果表明：(1)聚类算法可以很好地辅助分析早M型矮恒星的光谱数据,聚类产生的簇心数据和MK分类吻合得非常好。(2)三种不同聚类算法表现不尽相同,Bisecting K-Means在恒星光谱细分类方面更有优势。(3) 在聚类的同时也会产生一些数量较少的簇,从这些簇中可以发现一些稀有天体候选体,相对而言OPTICS适合用来寻找稀有天体候选体。     

无线传感器网络的分布式竞争路由算法

在WSNs体系结构中,路由算法是网络层的关键,分簇技术在路由算法中可提高WSNs的扩展性。提出一种竞争簇头,非均匀分簇和多跳路由相结合的WSNs 分布式竞争路由算法(DSA)．它的核心是构建一个高效的非均匀分簇算法,通过竞争的方式候选簇头,靠近基站的簇头为簇间的数据转发预留能量,根据节点的剩余能量、簇内和簇间通信代价,每个簇头在邻居簇头集中用贪心法确定中继节点,仿真表明,DSA算法能有效平衡了簇头的能耗、均衡了网络能耗、显著延长网络生存周期。