# Dissimilarity Matrix of non-metric proximity data

we currently have a coding exercise, where we are asked to implement Constant Shift Embedding (Paper). This in itself is not a big problem. For the algorithm, all you need is a symmetric non-zero diagonal dissimilarity matrix of some non-metric proximity data. With the algorithm you can then embed the information into a vector space and therefore you can use commonly known denoising and dimensionality reduction methods to improve the results of for example k-means clustering.

Given the E-Mail communications based on this data set, how would go about choosing a reasonable dissimilarity matrix?

The data is simply a list of unique pairs, where at least one e-mail has been sent from node A to node B. This gives rise to a graph of around 1000 nodes and 25000 edges.

Creating an adjacency matrix of this undirected graph might be a first step (which is also already provided in the framework).

I'm thankful for any pointers in the right direction.

EDIT: Over night I had an idea:

Let's say we only have 8 nodes. Now compare the proximity elements of two vertices. So if the prox. vectors would for example look like:

1 0 0 0 1 0 1 1

0 1 0 0 0 1 0 1

Their dissimilarity would be 5, since their vectors differ at 5 points.

Now just normalize w.r.t. the total number of nodes, therefore 5/8.

With this, we also incorporate the information of how many neighbors are shared instead of only looking at direct edges, and might therefore receive better results, when we later try to cluster the nodes.

Let me know what you think.

• Why is you matrix undirected? – Juan Esteban de la Calle Apr 30 '19 at 21:54
• Since it is not clear, who is the sender and who's the receiver. – ninji May 1 '19 at 8:26

Maybe I did not completely understand your question, but I think the answer you are looking for is one of the following:

• You may want to fill a n-by-n matrix with 1 if the person $$i$$ has sent e-mail(s) to person $$j$$, 0 otherwise

• Maybe you want to fill the n-by-n matrix with the number of emails sent from person $$i$$ to person $$j$$.

Both measures are distances in the mathematical definition.

For clarity:

You could program the dissimilarity matrix as $$M[i,j] = 1$$ if the pair of people in your data exists.

• Yes, I agree. Both measures can be used for the algorithm, just zero out the self-similarity if there is a 1 on the diagonal (meaning, someone sent a mail to himself in this context). The first bullet point is doable and already provided in the framework as a baseline. For the second one we lack information, since all pairs are unique so we do not know how many mails have been sent. – ninji May 1 '19 at 8:32