Joint Sequence Complexity Analysis: Application to Social Networks Information Flow - Archive ouverte HAL Access content directly
Journal Articles Bell Labs Technical Journal Year : 2014

Joint Sequence Complexity Analysis: Application to Social Networks Information Flow

(1, 2, 3, 4) , (1, 2)
1
2
3
4

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.
Not file

Dates and versions

hal-00907364 , version 1 (21-11-2013)

Identifiers

Cite

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

Altmetric

Share

Gmail Facebook Twitter LinkedIn More