Compare the SCAN algorithm (Section 9.5.3) with DBSCAN (Section 8.4.1). What are their similarities and differences? 9.5.3
Question:
Compare the SCAN algorithm (Section 9.5.3) with DBSCAN (Section 8.4.1). What are their similarities and differences?
Transcribed Image Text:
9.5.3 Graph clustering methods Let us consider how to conduct clustering on a graph. We first describe the intuition behind graph clustering. We then discuss two general categories of graph clustering methods. The intuition of finding clusters in a graph is to cut the graph into pieces, each piece being a cluster, such that the vertices within a cluster are well connected, and the vertices in different clusters are connected in a much weaker way. Formally, for a graph, G = (V, E), a cut, C = (S, T), is a partitioning of the set of vertices V in G, that is, V=SUT and SnT = . The cut set of a cut is the set of edges, {(u, v) E Elu ES, v E T}. The size of the cut is the number of edges in the cut set. For weighted graphs, the size of a cut is the sum of the weights of the edges in the cut set. "What kinds of cuts are good for deriving clusters in graphs?" In graph theory and some network applications, a minimum cut is of importance. A cut is minimum if the size of the cut is not greater than the size of any other cut. There are polynomial time algorithms to compute minimum cuts of graphs. Can we use those algorithms in graph clustering? Example 9.19. Cuts and clusters. Consider graph G in Fig. 9.17. The graph has two clusters: (a, b, c, d, e, f) and {g, h, i, j, k), and one outlier vertex, 1. Consider cut C = ({a, b, c, d, e, f, g, h, i, j, k}, {}). Only one edge, namely, (e, 1), crosses the two partitions created by C. Therefore the cut set of C is {(e,1)), and the size of C is 1. (Note that the size of any cut in a connected graph cannot be smaller than 1.) As a minimum cut, C does not lead to a good clustering because it only separates the outlier vertex, 1, from the rest of the graph. Cut C = ({a, b, c, d, e, f,l}, {g, h, i, j, k}) leads to a much better clustering than C. The edges in the cut set of C are those connecting the two "natural clusters" in the graph. Specifically, for edges (d, h) and (e, k) that are in the cut set, most of the edges connecting d, h, e, and k belong to one cluster.
Fantastic news! We've Found the answer you've been seeking!
Step by Step Answer:
Answer rating: 100% (QA)
Based on the information from the images provided we can compare SCAN Structural Clustering Algorithm for Networks and DBSCAN DensityBased Spatial Clu...View the full answer
Answered By
Sumit kumar
Education details:
QUATERNARY Pursuing M.Tech.(2017-2019) in Electronics and Communication Engg. (VLSI DESIGN) from
GNIOT Greater Noida
TERTIARY B.Tech. (2012-2016) in Electronics and Communication Engg. from GLBITM Greater Noida
SECONDARY Senior Secondary School Examination (Class XII) in 2012 from R.S.S.Inter College, Noida
ELEMENTARY Secondary School Examination (Class X) in 2010 from New R.J.C. Public School ,Noida
CERTIFICATION
Summer Training in ‘WIRELESS EMBEDDED SYSTEM’ from ‘XIONEE’ for the six weeks.
EMBEDDED SYSTEM Certificate issued by CETPA INFOTECH for one day workshop.
Certificate of Faculty development program on OPTICAL COMMUNICATION and NETWORKS for one week.
5.00+
1+ Reviews
10+ Question Solved
Related Book For
Data Mining Concepts And Techniques
ISBN: 9780128117613
4th Edition
Authors: Jiawei Han, Jian Pei, Hanghang Tong
Question Posted:
Students also viewed these Computer science questions
-
Defining the Problem (1). Lead is an environmental pollutant especially worthy of attention because of its damaging effects on the neurological and intellectual development of children. Morton et al....
-
The following additional information is available for the Dr. Ivan and Irene Incisor family from Chapters 1-5. Ivan's grandfather died and left a portfolio of municipal bonds. In 2012, they pay Ivan...
-
"If nominal GDP rises, velocity must rise." Is this statement true, false, or uncertain? Explain your answer.
-
A 19.5-ft ladder AB leans against a wall as shown. Assuming that the coefficient of static friction s μ is the same at A and B, determine the smallest value of s μ for which equilibrium is...
-
55 keV x-ray photons are incident on a target. At what scattering angle do the scattered photons have an energy of 50 keV?
-
Refer to the information in Exercise 16-14. Prepare journal entries dated June 30 to record: (a) raw materials purchases, (b) direct materials usage, (c) indirect materials usage, (d) direct labor...
-
Presented below are the closing entries for Lee College, a private not-for-profit, for the year ended December 31, 2012. Assume the January 1, 2012, net asset balances are as follows: $1,000,000...
-
1. The rate at which a bean plant grows is given by a differentiable function R(t). measured in centimeters per day, where 0 st s 30. A graph of the function R is shown below along with a table of...
-
Consider partitioning clustering and the following constraint on clusters: The number of objects in each cluster must be between \(\frac{n}{k}(1-\delta)\) and \(\frac{n}{k}(1+\delta)\), where \(n\)...
-
In a large sparse graph where on average each node has a low degree, is the similarity matrix using SimRank still sparse? If so, in what sense? If not, why? Deliberate on your answer.
-
Referring to Question 2.44, would the offset method be necessary for a highly strained-hardened material? Explain.
-
In what ways does neuroplasticity contribute to an individual's ability to adapt to novel circumstances and challenges?
-
With Tranquilifeet, Bayer can achieve their goal of improving thequality of life of their patients by lowering stress and anxiety through a medicine-free treatment. This treatment is cost-effective...
-
Have you as a consumer seen or participated in omnichannel retail shopping? If so, share your shopping experience. Specifically, what did you like about buying from the same retailer on multiple...
-
You are an investor currently considering purchasing shares of Rody Inc. You expect them to pay a dividend of $2.13 a share and those dividends to grow at 2% a year indefinitely, however, you dont...
-
What ethical considerations arise in the context of emerging technologies, such as artificial intelligence and biotechnology, and how can organizations proactively address these challenges to uphold...
-
"The following information is available for Remmers Corporation for 2010. 1. Depreciation reported on the tax return exceeded depreciation reported on the income statement by" $120,000. This...
-
Establish identity. cos( + k) = (-1)k cos , k any integer
-
The thickness of a conductive coating in micrometers has a density function of 600x-2 for 100 m < x <120 m. (a) Determine the mean and variance of the coating thickness. (b) If the coating costs...
-
Suppose that contamination particle size (in micrometers) can be modeled as for Determine the mean of X.
-
Integration by parts is required. The probability density function for the diameter of a drilled hole in millimeters is for mm. Although the target diameter is 5 millimeters, vibrations, tool wear,...
-
A compressor running at 350 rpm is driven by a 120 kW motor running at 1400 rpm. The center distance is 400 mm (Approx.) and helix angle is 25. The motor pinion is made of forged steel 0.30% C...
-
What do you label retained earnings as if it's not an option?? Would it be service revenue?
-
Why should student affairs administrators at universities implement or fund financial aid workshops for first-generation college students?
Study smarter with the SolutionInn App