Communities of interest. (English) Zbl 1029.68692

Cortes, Corinna; Pregibon, Daryl; Volinsky, Chris

Hoffmann, Frank (ed.) et al., Advances in intelligent data analysis. 4th international conference, IDA 2001, Cascais, Portugal, September 13-15, 2001. Proceedings. Berlin: Springer. Lect. Notes Comput. Sci. 2189, 105-114 (2001).

Summary: We consider problems that can be characterized by large dynamic graphs. Communication networks provide the prototypical example of such problems where nodes in the graph are network IDs and the edges represent communication between pairs of network IDs. In such graphs, nodes and edges appear and disappear through time so that methods that apply to static graphs are not sufficient. We introduce a data structure that captures, in an approximate sense, the graph and its evolution through time. The data structure arises from a bottom-up representation of the large graph as the union of small subgraphs, called Communities of Interest (COI), centered on every node. These subgraphs are interesting in their own right and we discuss two applications in the area of telecommunications fraud detection to help motivate the ideas.
For the entire collection see [Zbl 0977.68809].

MSC:

68U99	Computing methodologies and applications
68T05	Learning and adaptive systems in artificial intelligence