Joint Sequence Complexity Analysis: Application to Social Networks Information Flow

Abstract : In this paper we study joint sequence complexity and its applications for finding similarities between sequences up to the discrimination of sources. The mathematical concept of the complexity of a sequence is defined as the number of distinct subsequences of it. Sequences containing many common parts have a higher joint complexity. The analysis of a sequence in subcomponents is done by suffix trees, which is a simple, fast, and low complexity method to store and recall them from the memory, especially for short sequences. Joint complexity is used for evaluating the similarity between sequences generated by different Markov sources. Markov models well describe the generation of natural text, and their performance can be predicted via linear algebra, combinatorics, and asymptotic analysis. We exploit datasets from different natural languages, for both short and long sequences, with very promising results. The goal is to perform automated online sequence analysis on information streams, e.g., on social networks such as Twitter.
Document type :
Journal articles
Complete list of metadatas

https://hal-polytechnique.archives-ouvertes.fr/hal-00907364
Contributor : Dimitrios Milioris <>
Submitted on : Thursday, November 21, 2013 - 10:48:47 AM
Last modification on : Wednesday, May 15, 2019 - 4:05:29 AM

Identifiers

Citation

Dimitrios Milioris, Philippe Jacquet. Joint Sequence Complexity Analysis: Application to Social Networks Information Flow. Bell Labs Technical Journal, Wiley, 2014, 18 (4), pp.75-88. ⟨10.1002/bltj.21647⟩. ⟨hal-00907364⟩

Share

Metrics

Record views

721