Extraction of Community Transition Rules from Data Streams as Large Graph Sequence
Takehiro Yamaguchi* and Ayahiko Niimi**
*Graduate School of Systems Information Science, Future University Hakodate
**Department of Media Architecture, Faculty of Systems Information Science, Future University Hakodate, 116-2 Kamedanakano, Hakodate, Hokkaido 041-8655, Japan
In this study, we treat transactional sets of data streams as a graph sequence. This graph sequence represents both the relational structures of data for each period and changes in these structures. In addition, we analyze changes in a community in this graph sequence. Our proposed algorithm extracts community transition rules to detect communities that appear irregularly in a graph sequence using our proposed method combined with adaptive graph kernels and hierarchical clustering. In experiments using synthetic datasets and social bookmark datasets, we demonstrate that our proposed algorithm detects changes in a community appearing irregularly.
-  H. Arimura, “Recent Development of Mining Algorithms for Data Streams,” The Trans. of the Institute of Electronics, Information and Communication Engineers, D-I J88-D-I(3), pp. 563-575, 2005.
-  M. Toyoda and M. Kitsuregawa, “Extracting Evolution of Web Communities from a Series of Web Archives,” Proc. of the 14th ACM Conf. on Hypertext and Hypermedia (Hypertext 03), 2003.
-  M. Gupta, C. Aggarwal, J. Han, and Y. Sun, “Evolutionary Clustering and Analysis of Heterogeneous Information Networks,” IBM Research Report, RC25012 (W1006-064) June 17, 2010.
-  Y. Lin, Y. Chi, S. Zhu, H. Sundaram, and B. L. Tseng, “FacetNet: a framework for analyzing communities and their evolutions in dynamic networks,” Proc. of the 17th Int. Conf. on World Wide Web, pp. 685-694, 2008.
-  Y. Chi, X. Song, D. Zhou, K. Hino, and B. L. Tseng, “On Evolutionary Spectral Clustering,” ACM Trans. on Knowledge Discovery from Data, Vol.3, No.4, Article 17, 2009.
-  M. Girvan and M. Newman, “Community structure in social and biological networks,” Proc. of the National Academy of the United States of America, Vol.99, No.12, pp. 7821-7826, 2002.
-  A. Clauset, M. E. J. Newman, and C. Moore, “Finding community structure in very large networks,” Physical Review E, Vol.70, p. 066111, 2004.
-  J. Shawe-Taylor and N. Cristianini, “Kernel Methods for Pattern Analysis,” Cambridge University Press, 2004.
-  A. Niimi and O. Konishi, “Parallel Boosting with Stream Kernel Machine,” IPSJ Trans. on Databases, Vol.2, No.4, pp. 13-23, 2009.
-  M. Tsuzuki and O. Konishi, “Adaptive Kernel Methods in Largescale Data Stream with Historical Information,” IPSJ Trans. on Databases, Vol.1, No.3, pp. 49-59, 2008.
-  H. Kashima, K. Tsuda, and A. Inokuchi, “Marginalized Kernels for Labeled Graphs,” Proc. of the 20th Int. Conf. on Machine Learning, pp. 321-328, 2003.
-  T. Yamaguchi and A. Niimi, “Time-Series Analysis of Communities using Association Rule in Data Streams,” The 24th Annual Conf. of the Japanese Society for Artificial Intelligence, 2010.
-  T. Yamaguchi and A. Niimi, “Time-Series Analysis Communities using Adaptive Graph Kernels in Data Streams,” Proc. of Joint 5th Int. Conf. on Soft Computing and Intelligent Systems and 11th Int. Symposium on advanced Intelligent Systems (SCIS & ISIS2010), 2010.
-  M. E. J. Newman and M. Girvan, “Finding and evaluating community structure in networks,” PHYSICAL REVIEW E, Vol.69, p. 026113, 2004.
-  EDGE Datasets, http://labs.edge.jp/datasets/ (As of Jan, 2011).