Finding conversation blocks in group chat

Question

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.

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.