Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userA Novel Algorithm for Informative Meta Similarity Clusters Using Minimum Spanning Tree
107
0
0.0
(
0
)
Added by
Rdv Ijcsis
Publication date
2010
fields
Informatics Engineering
and research's language is
English
Ask ChatGPT about the research
No Arabic abstract
The minimum spanning tree clustering algorithm is capable of detecting clusters with irregular boundaries. In this paper we propose two minimum spanning trees based clustering algorithm. The first algorithm produces k clusters with center and guaranteed intra-cluster similarity. The radius and diameter of k clusters are computed to find the tightness of k clusters. The variance of the k clusters are also computed to find the compactness of the clusters. The second algorithm is proposed to create a dendrogram using the k clusters as objects with guaranteed inter-cluster similarity. The algorithm is also finds central cluster from the k number of clusters. The first algorithm uses divisive approach, where as the second algorithm uses agglomerative approach. In this paper we used both the approaches to find Informative Meta similarity clusters.
rate research
Read More
Given an undirected, weighted graph, the minimum spanning tree (MST) is a tree that connects all of the vertices of the graph with minimum sum of edge weights. In real world applications, network designers often seek to quickly find a replacement edge for each edge in the MST. For example, when a traffic accident closes a road in a transportation network, or a line goes down in a communication network, the replacement edge may reconnect the MST at lowest cost. In the paper, we consider the case of finding the lowest cost replacement edge for each edge of the MST. A previous algorithm by Tarjan takes $O(m alpha(m, n))$ time, where $alpha(m, n)$ is the inverse Ackermanns function. Given the MST and sorted non-tree edges, our algorithm is the first that runs in $O(m+n)$ time and $O(m+n)$ space to find all replacement edges. Moreover, it is easy to implement and our experimental study demonstrates fast performance on several types of graphs. Additionally, since the most vital edge is the tree edge whose removal causes the highest cost, our algorithm finds it in linear time.
Cosmological studies of large-scale structure have relied on two-point statistics, not fully exploiting the rich structure of the cosmic web. In this paper we show how to capture some of this cosmic web information by using the minimum spanning tree (MST), for the first time using it to estimate cosmological parameters in simulations. Discrete tracers of dark matter such as galaxies, $N$-body particles or haloes are used as nodes to construct a unique graph, the MST, that traces skeletal structure. We study the dependence of the MST on cosmological parameters using haloes from a suite of COLA simulations with a box size of $250 h^{-1}{rm Mpc}$, varying the amplitude of scalar fluctuations $left(A_{rm s}right)$, matter density $left(Omega_{rm m}right)$, and neutrino mass $left(sum m_{ u}right)$. The power spectrum $P$ and bispectrum $B$ are measured for wavenumbers between $0.125$ and $0.5$ $h{rm Mpc}^{-1}$, while a corresponding lower cut of $sim12.6$ $h^{-1}{rm Mpc}$ is applied to the MST. The constraints from the individual methods are fairly similar but when combined we see improved $1sigma$ constraints of $sim 17%$ ($sim 12%$) on $Omega_{rm m}$ and $sim 12%$ ($sim 10%$) on $A_{rm s}$ with respect to $P$ ($P+B$) thus showing the MST is providing additional information. The MST can be applied to current and future spectroscopic surveys (BOSS, DESI, Euclid, PSF, WFIRST, and 4MOST) in 3D and photometric surveys (DES and LSST) in tomographic shells to constrain parameters and/or test systematics.
We present a novel self-stabilizing algorithm for minimum spanning tree (MST) construction. The space complexity of our solution is $O(log^2n)$ bits and it converges in $O(n^2)$ rounds. Thus, this algorithm improves the convergence time of all previously known self-stabilizing asynchronous MST algorithms by a multiplicative factor $Theta(n)$, to the price of increasing the best known space complexity by a factor $O(log n)$. The main ingredient used in our algorithm is the design, for the first time in self-stabilizing settings, of a labeling scheme for computing the nearest common ancestor with only $O(log^2n)$ bits.
In a geometric network G = (S, E), the graph distance between two vertices u, v in S is the length of the shortest path in G connecting u to v. The dilation of G is the maximum factor by which the graph distance of a pair of vertices differs from their Euclidean distance. We show that given a set S of n points with integer coordinates in the plane and a rational dilation delta > 1, it is NP-hard to determine whether a spanning tree of S with dilation at most delta exists.
This paper presents a spanning tree-based genetic algorithm (GA) for the reconfiguration of electrical distribution systems with the objective of minimizing active power losses. Due to low voltage levels at distribution systems, power losses are high and sensitive to system configuration. Therefore, optimal reconfiguration is an important factor in the operation of distribution systems to minimize active power losses. Smart and automated electric distribution systems are able to reconfigure as a response to changes in load levels to minimize active power losses. The proposed method searches spanning trees of potential configurations and finds the optimal spanning tree using a genetic algorithm in two steps. In the first step, all invalid combinations of branches and tie-lines (i.e., switching combinations that do not provide power to some of loads or violate the radiality and connectivity conditions) generated by initial population of GA are filtered out with the help of spanning-tree search algorithm. In the second step, power flow analyses are performed only for combinations that form spanning trees. The optimal configuration is then determined based on the amount of active power losses (optimal configuration is the one that results in minimum power losses). The proposed method is implemented on several systems including the well-known 33-node and 69-node systems. The results show that the proposed method is accurate and efficient in comparison with existing methods.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
