While analysing an IM group chat, the aim is to create a network with nodes as the group participants and the links corresponding to their conversations.

Assuming that this chat has conversation blocks, wherein some members participate in each such block. For a particular block, a link would be put up between each of the participants, (if ABC participated, A-B, B-C, A-C would be the links), and the process repeated over the entire time the group existed. Not all members participate equally frequently, and some preferentially with a select few, a structure that would be apparent in the resultant network. A time evolving network would be the desired goal.

Problem is to delineate these blocks. We have information of the time of each message and its sender (overlooking the text, since that'd add another level of complexity)

I thought of using a 1-D Density based clustering (like DBSCAN), since conversations would be high density regions in time separated by intervening low density time gaps. But then not all blocks would have the same density. Is there a variable density option?

Another problem is to validate these clusters. I am aware of silhouettes and CH criteria, both of which are not traditionally used in density based non-globose clustering. Is there any validation tool for Density based clustering?

Any idea on the main problem, or to improve the efficiency of this delineation compared to simple clustering (eg: accommodating better noise identifiers, etc) are welcome.

And the I am comfortable with R and moderately with Python, if the tools can be narrowed down.


1 Answer 1


For one dimensional data, k would generally prefer density estimation techniques from statistics such as Kernel Density Estimation over clustering methods such as DBSCAN. The big benefit of DBSCAN is the scalability to large data sets by indexing. But one dimensional data can be sorted, and that makes a lot more approaches applicable and scalable in a wah that beats any such index.

By using KDE you get much more theoretical support into your model.

Wrt. Evaluation of density clustering: yes, such measures exist. See the DBCV paper:

Moulavi, D., Jaskowiak, P. A., Campello, R. J., Zimek, A., & Sander, J. (2014, April).
Density-based clustering validation.
In Proceedings of the 2014 SIAM International Conference on Data Mining (pp. 839-847). Society for Industrial and Applied Mathematics.

  • $\begingroup$ I looked up using KDE for clustering. Basically, afaik, we use minimas as breaks between clusters. But then this would be bandwidth sensitive. How do we choose it appropriately? $\endgroup$ Jul 5, 2017 at 8:46
  • $\begingroup$ Also. Validation of KDE based clusters? $\endgroup$ Jul 5, 2017 at 8:47
  • $\begingroup$ There are very good heuristics from statistics literature for choosing the bandwidth, much better heuristics than for choosing DBSCAN parameters. There is nothing preventing you from doing the same kind of evaluation, but I'd assume there are also special evaluation techniques for KDE. $\endgroup$ Jul 5, 2017 at 10:38

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.