A Random Walk through Human Associations Raz Tamir   View Paper (PDF)   Return to Session 18: Statistical Methods II Abstract Letting one's thoughts wander is not simply an arbitrary or rambling process. It can better be described as "associative thinking", where a complex chain of associative thoughts and ideas are linked. It is our contention that this seemingly chaotic process can be modeled by a random walk in a weighted directed graph. Furthermore, is it possible to predict mathematically the "steady state" of such a process, to determine where such wandering is leading. The random walk process uses rules of association, defined by the Local Confidence Gain (LCG) interestingness measure. Extracted concepts are used as nodes of a directed graph. The associative "forces" between any two concepts (measured by LCG) are used to weigh the edges connecting the nodes that create a graph of associations. It is common, yet not trivial, for people to look for data about a subject without knowing its exact nomenclature (for example, finding the name of a disease just by knowing its symptoms). Random walk in association graphs can discover highly informative phrases that can be used for query expansion in a way that better expresses the user's initial search goals. A different usage is to create a user profile representing his current interests. We used a modified version of the Turing Test to show that the random walk process discovers association rules that conform to a human associations generating process. By constructing the user associations we were able to build a profile representing the user's "line of thoughts". The suggested algorithm can be used in any database and can implement the ranking measures of other association rules. ©2006 Association for Computing Machinery