Top > JACIII > Extraction of Community Transition Rules from Data Streams as ...

single-jc.php

JACIII Vol.15 No.8 pp. 1073-1081
doi: 10.20965/jaciii.2011.p1073
(2011)

Paper:

Views over last 60 days: 623

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

Received:
March 7, 2011
Accepted:
July 15, 2011
Published:
October 20, 2011
Creative Commons License
Keywords:
graph sequence, community transition rules, graph kernels, clustering, social bookmark
Abstract
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.
Cite this article as:
T. Yamaguchi and A. Niimi, “Extraction of Community Transition Rules from Data Streams as Large Graph Sequence,” J. Adv. Comput. Intell. Intell. Inform., Vol.15 No.8, pp. 1073-1081, 2011.
Data files:
References
  1. [1] 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.
  2. [2] 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.
  3. [3] 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.
  4. [4] 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.
  5. [5] 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.
  6. [6] 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.
  7. [7] A. Clauset, M. E. J. Newman, and C. Moore, “Finding community structure in very large networks,” Physical Review E, Vol.70, p. 066111, 2004.
  8. [8] J. Shawe-Taylor and N. Cristianini, “Kernel Methods for Pattern Analysis,” Cambridge University Press, 2004.
  9. [9] A. Niimi and O. Konishi, “Parallel Boosting with Stream Kernel Machine,” IPSJ Trans. on Databases, Vol.2, No.4, pp. 13-23, 2009.
  10. [10] 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.
  11. [11] 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.
  12. [12] 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.
  13. [13] 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.
  14. [14] M. E. J. Newman and M. Girvan, “Finding and evaluating community structure in networks,” PHYSICAL REVIEW E, Vol.69, p. 026113, 2004.
  15. [15] EDGE Datasets, http://labs.edge.jp/datasets/ (As of Jan, 2011).

Creative Commons License  This article is published under a Creative Commons Attribution-NoDerivatives 4.0 Internationa License.

*This site is desgined based on HTML5 and CSS3 for modern browsers, e.g. Chrome, Firefox, Safari, Edge, Opera.

Last updated on Dec. 06, 2024