v 1 v 2 e g ˆ Š Œ Ž p š ~ m n u { i 1, i 2, i 3, i 4 } { i 1, i 5 } v 1 v 2 v 3 v 4 v 5 v 6 { i 1, i 2, i 4 } { i 1, i 2, i 3, i 5 } { i 1, i 3, i 4 }

Size: px

Start display at page:

Download "v 1 v 2 e g ˆ Š Œ Ž p š ~ m n u { i 1, i 2, i 3, i 4 } { i 1, i 5 } v 1 v 2 v 3 v 4 v 5 v 6 { i 1, i 2, i 4 } { i 1, i 2, i 3, i 5 } { i 1, i 3, i 4 }"

ふさこののした
5 years ago
Views:

1 DEIM Forum 2009 D2-1 COPINE: {seki,sesejun}@sel.is.ocha.ac.jp COPINE COPINE: Mining Networks Sharing Common Patterns Mio SEKI and Jun SESE Graduate School of Humanities and Sciences, Ochanomizu University Otsuka 2 1 1, Bunkyo-ku, Tokyo, Japan {seki,sesejun}@sel.is.ocha.ac.jp Abstract We specifically examine an undirected network where nodes have a set of items, such as a social network in which the nodes are associated with each person s bought products or a gene network in which the nodes are related to each gene s activated conditions. For a given network, the subnetworks whose vertices contain common patterns have various applications. In order to extract such subnetworks, we introduce an algorithm called COPINE. COPINE can extract subnetworks from network having ten thousand nodes and two hundred thousand edges. COPINE can also discover useful biological networks from protein-protein interaction network in yeast. Key words Graph mining, common patterns 1. [1] 2 COmmon Pattern Itemset NEtwork mining (COPINE)

2 v 1 v 2 e g ˆ Š Œ Ž p š ~ m n u { i 1, i 2, i 3, i 4 } { i 1, i 5 } v 1 v 2 v 3 v 4 v 5 v 6 { i 1, i 2, i 4 } { i 1, i 2, i 3, i 5 } { i 1, i 3, i 4 } { i 1, i 3, i 5 } e f g h i j k l m n v 1 v 2 e o g h i j k l m n { i 1, i 2 } p q r s t u v w x y z { } ~ m n u v 1 v 2 e œ g h i j k l m n { i 1, i 3 } p q r s t u v w x y z { } ~ m n u 1(A) 1(B) 1(C)(D) 1(A)(B) 1(C) {i 1, i 2 } 1(D) {i 1, i 3 } G G G 1(C)(D) N n 1 v 1 : { i 1, i 2, i 3, i 4 } v 2 : { i 1, i 5 } v 3 : { i 1, i 2, i 4 } n 2 v 2 : { i 1 } v 3 : { i 1, i 2, i 4 } v 4 : { i 1, i 2, i 3 } v 6 : { i 1, i 3 } v 3 : { i 1 } n 4 v 2 : { i 1 } v 4 : { i 1, i 2 } v 3 : { i 1, i 2 } v 5 : { i 1, i 3 } v 6 : { i 1, i 3 } n 3 v 5 : { i 1 } v 6 : { i 1 } v 6 : { i 1, i 3 } 2 DFS N N COPINE COPINE COPINE (A)(B) COPINE 2 1 v 1 v 1 {i 1, i 2, i 3, i 4 } n 1 v 2 n 1 v 2 v 1 v 2 {i 1 } n 2 n 2 {i 1 } 2 n (A) v 6 < v 1, v 4, v 5, v 6 > < v 1, v 4, v 6 > < v 1, v 6 >

3 v P(v) v 1 {i 1, i 2, i 3, i 4 } v 3 {i 1, i 2, i 4 } v 4 {i 1, i 2 }, {i 1, i 2, i 3 } v 5 {i 1, i 3 } v 6 {i 1, i 3 } 1 ( 2 n 3 ) 2 V 1,000 E 5,000 N 0 T 20 I L 20 θ I n 1 n 2 n 1 n 2 n 1 n 2 n 2 n 1 n n 3 1 P(v 3) v 3 {i 1, i 2, i 4} v P(v) 2 n n 4 v 6 {i 1, i 3} P(v 6) = {i 1, i 3} COPINE COPINE Java Java CPU AMD Opteron 2.2GHz OS Linux2.6 COPINE 1GB COPINE 2 COPINE 1 V 2 2 E 3 I 4 (3) (1) 1 v 5 v 1 v (3) v v (3) L 6 T COPINE COPINE 3 COPINE w/o Crossed Patterns Table, COPINE 3(A) COPINE 3(B) 1 COPINE COPINE 4(A) COPINE COPINE (B) 1 COPINE COPINE

4 0 w/o Crossed Patterns Table COPINE 0 w/o Crossed Patterns Table COPINE E / V : Average degree L : Answer network size (A) 3 (B) V =,000 V = 5,000 V = 2,000 V = 1, E = 20,000 E = 15,000 E =,000 E = 5,000 E = 2, E / V :Average degree L : Answer network size (A) 4 COPINE (B) 4(B) , 2.3 overlap(g 1, G 2 ) E(G 1 ) E(G 2 ) min { E(G 1 ), E(G 2 ) } I(G 1 ) I(G 2 ) min { I(G 1 ), I(G 2 ) }, G 1 G 2 E(G 1 ) I(G 1 ) G 1 overlap(g 1, G 2 ) 0 1 G 1 G 2 1 γ overlap(g 1, G 2 ) > γ 7,564 [2 4] 173 6,152 [5] 1.0 θ = 3 COPINE γ = COPINE [6, 7] p COPINE 4. [8,9] [] [11] 1 2

5 1 Apriori [12] FP-tree [13] 5. COPINE COPINE COPINE COPINE COPINE COPINE [1] M. E. J. Newman. The structure and function of complex networks. SIAM Review, 45:167, 2003. [2] T. Ito, et al.

A comprehensive analysis of protein-protein interactions in Saccharomyces cervisiae. Nature, vol. 403, no. 6770, 623-627, 2000. [4] N. J. Krogan, et al.

5 5 1 Apriori [12] FP-tree [13] 5. COPINE COPINE COPINE COPINE COPINE COPINE [1] M. E. J. Newman. The structure and function of complex networks. SIAM Review, 45:167, [2] T. Ito, et al. A comprehensive two-hybrid analysis to explore the yeast protein interactome. Proc. Natl.Acad. Sci. vol. 98, , [3] P. Uetz, et al. A comprehensive analysis of protein-protein interactions in Saccharomyces cervisiae. Nature, vol. 403, no. 6770, , [4] N. J. Krogan, et al. Global landscape of protein complexes in the yeast Saccharomyces cerevisiae. Nature, vol. 440, , [5] A. P. Gasch, et al. Genomic expression programs in the response of yeast cells to environmental changes. Mol. Biol. Cell, vol. 11, no. 12, , [6] M. Ashburner, et al. Gene ontology: tool for the unification of biology. the gene ontology consortium. Nat Genet, vol. 25, no. 1, 25-29, May [7] M. Kanehisa, and S. Goto. KEGG: Kyoto Encyclopedia of Genes and Genomes. Nucleic Acids Res, 28: 27-30, [8] A. Inokuchi, T. Washio, and H. Motoda. An apriori-based algorithm for mining frequent substructures from graph data. PKDD 00, [9] X. Yan and J. Han. gspan: Graph-Based Substructure Pattern Mining. ICDM 02, 721, [] M. J. Rattigan, M. Maier, and D. Jensen. Graph clustering with network structure indices. ICML 07, , [11] M. Shiga, I. Takigawa, and H. Mamitsuka. A spectral clustering approach to optimally combining numerical vectors with a modular network. KDD 07, , [12] R. Agrawal and R. Srikant. First algorithms for mining association rules. Proc. VLDB 94, , [13] J. Han, J. Pei, and Y. Yin. Mining frequent patterns without candidate generation. Proc. SIGMOD 00, 1-12, 2000.

DEIM Forum 2009 C8-4 QA NTT QA QA QA 2 QA Abstract Questions Recomme

DEIM Forum 2009 C8-4 QA NTT QA QA QA 2 QA Abstract Questions Recomme DEIM Forum 2009 C8-4 QA NTT 239 0847 1 1 E-mail: {kabutoya.yutaka,kawashima.harumi,fujimura.ko}@lab.ntt.co.jp QA QA QA 2 QA Abstract Questions Recommendation Based on Evolution Patterns of a QA Community