اشترك بالحزمة الذهبية واحصل على وصول غير محدود شمرا أكاديميا
تسجيل مستخدم جديدA Novel Algorithm for Informative Meta Similarity Clusters Using Minimum Spanning Tree
105
0
0.0
(
0
)
اسأل ChatGPT حول البحث
ﻻ يوجد ملخص باللغة العربية
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.
قيم البحث
اقرأ أيضاً
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 edg
e 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 previo
usly 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 the
ir 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.
سجل دخول لتتمكن من نشر تعليقات
التعليقات
جاري جلب التعليقات
سجل دخول لتتمكن من متابعة معايير البحث التي قمت باختيارها
