Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

add vertex itself to nodes' neighborhood in PSCAN #23

Open
dawnranger opened this issue Aug 23, 2018 · 0 comments
Open

add vertex itself to nodes' neighborhood in PSCAN #23

dawnranger opened this issue Aug 23, 2018 · 0 comments

Comments

@dawnranger
Copy link

The neighborhood of each node in PSCAN should contain itself.

The neighborhood of a vertex is defined in the paper of SCAN:

DEFINITION 1 (VERTEX STRUCTURE)
Let v ∈ V, the structure of v is defined by its neighborhood,
denoted by Γ(v)
Γ(v) = {w ∈ V | (v,w) ∈ E} ∪ {v}
In Figure 1 vertex 6 is a hub sharing neighbors with two clusters.
If we only use the number of shared neighbors, vertex 6 will be
clustered into either of the clusters or cause the two clusters to
merge. Therefore, we normalize the number of common neighbors
by the geometric mean of the two neighborhoods’ size.

If vertex itself is not contained, similarities of all node pairs will be smaller than the expected value.

For example, if two connected vertices have no common neighbors, the similarity will be 0. Which is the same as node pairs that are not connected by an edge. This is apparently not correct.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
None yet
Projects
None yet
Development

No branches or pull requests

1 participant