How do we know the weight of a node or edge when we are doing clustering on density basis in a simple undirected graph. And what's time complexity here!
can you guide me from here:
The weight of an edge (u,v) E ∈ is the number of the common neighbors of the nodes u and v. M^2 for u≠v represents the number of common neighbor of the nodes u and v. The timing complexity of matrix multiplication is of the order N^3. However, we need only those elements of M^2 for which M(u,v) =1 . So the complexity of finding weights of the edges can be reduced to O(N*E).
The weight of a node is the sum of the weights of the edges connected to the node. The weight of every node is calculated and then the highest weight node is determined. The complexity of finding the weights of the nodes is N^2 . We start at the highest weight node as the cluster and then grow it larger.
if you understand it guide me ...
By timing complexity, they really mean computational complexity, which is expressed in Big-O notation, as shown in answer (1) in your post: O(N.E).
The weight of an edge is what you decide to assign to it - it is part of the problem definition. In the travelling salesman problem, it would be the length of the journey, e.g. in miles or kilometers.