TY - GEN

T1 - Computational methods to discover sets of patterns of behaviors that precede political events of interest

AU - Rohloff, Kurt

AU - Asal, Victor

PY - 2009/11/5

Y1 - 2009/11/5

N2 - In this paper we present an approach to identify sets of patterns of behaviors which precede political events of interest (Eols) such as the the onset of regime change, insurgency, ethnic violence, etc.. We define a pattern to be an identified set of values of sampled, quantized factor data which occurs before at least two instances of an Eol and only before the occurrences of Eols. Not all Eols instances exhibit the same patterns preceding their occurrence, but we hypothesize that there exist sets of patterns which, taken together, precede all Eols of the same type. A set of patterns which taken together precede all Eols of the same type are called a "cover". We describe a computationally efficient cover discovery operation based on a randomized greedy algorithm which grows patterns simultaneously with the cover. This cover discovery algorithm was implemented in the Java programming language. Although the optimal cover discovery problem is NP-complete, our al-gorithm runs in polynomial time and returns nontrivial results.

AB - In this paper we present an approach to identify sets of patterns of behaviors which precede political events of interest (Eols) such as the the onset of regime change, insurgency, ethnic violence, etc.. We define a pattern to be an identified set of values of sampled, quantized factor data which occurs before at least two instances of an Eol and only before the occurrences of Eols. Not all Eols instances exhibit the same patterns preceding their occurrence, but we hypothesize that there exist sets of patterns which, taken together, precede all Eols of the same type. A set of patterns which taken together precede all Eols of the same type are called a "cover". We describe a computationally efficient cover discovery operation based on a randomized greedy algorithm which grows patterns simultaneously with the cover. This cover discovery algorithm was implemented in the Java programming language. Although the optimal cover discovery problem is NP-complete, our al-gorithm runs in polynomial time and returns nontrivial results.

UR - http://www.scopus.com/inward/record.url?scp=70350539054&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=70350539054&partnerID=8YFLogxK

M3 - Conference contribution

AN - SCOPUS:70350539054

SN - 9781577354161

T3 - AAAI Spring Symposium - Technical Report

SP - 126

EP - 129

BT - Technosocial Predictive Analytics - Papers from the AAAI Spring Symposium

T2 - 2009 AAAI Spring Symposium

Y2 - 23 March 2009 through 25 March 2009

ER -