K-Connected Cores Computation in Large Dual Networks
Tóm tắt
Computing $$k\text {-}core$$ s is a fundamental and important graph problem, which can be applied in many areas, such as community detection, network visualization, and network topology analysis. Due to the complex relationship between different entities, dual graph widely exists in the applications. A dual graph contains a physical graph and a conceptual graph, both of which have the same vertex set. Given that there exist no previous studies on the $$k\text {-}core$$ in dual graphs, we formulate a k-connected core ( $$k\text {-}CCO$$ ) model in dual graphs. A $$k\text {-}CCO$$ is a $$k\text {-}core$$ in the conceptual graph, and also connected in the physical graph. Given a dual graph and an integer k, we propose a polynomial time algorithm for computing all $$k\text {-}CCO$$ s. We also propose three algorithms for computing all maximum-connected cores ( $$MCCO$$ ), which are the existing $$k\text {-}CCO$$ s such that a $$(k+1)$$ - $$CCO$$ does not exist. We further study a subgraph search problem, which is computing a $$k\text {-}CCO$$ that contains a set of query vertices. We propose an index-based approach to efficiently answer the query for any given parameter k. We conduct extensive experiments on six real-world datasets and four synthetic datasets. The experimental results demonstrate the effectiveness and efficiency of our proposed algorithms.
Tài liệu tham khảo
Alvarez-Hamelin JI, Dall’Asta L, Barrat A, Vespignani A (2006) Large scale networks fingerprinting and visualization using the k-core decomposition. In: NIPS, pp 41–50
citation_journal_title=J Algorithms; citation_title=Greedily finding a dense subgraph; citation_author=Y Asahiro, K Iwama, H Tamaki, T Tokuyama; citation_volume=34; citation_issue=2; citation_publication_date=2000; citation_pages=203-221; citation_doi=10.1006/jagm.1999.1062; citation_id=CR2
Batagelj V, Zaversnik M (2003) An o(m) algorithm for cores decomposition of networks. arXiv preprint cs/0310049
Bonchi F, Gullo F, Kaltenbrunner A, Volkovich Y (2014) Core decomposition of uncertain graphs. In: KDD, pp 1316–1325
Chang L, Yu JX, Qin L, Lin X, Liu C, Liang W (2013) Efficiently computing k-edge connected components via graph decomposition. In: SIGMOD, pp 205–216
Charikar M (2000) Greedy approximation algorithms for finding dense components in a graph. In: APPROX, pp 84–95
Cheng J, Ke Y, Chu S, Tamer Özsu M (2011) Efficient core decomposition in massive networks. In: ICDE, pp 51–62
Cho E, Myers SA, Leskovec J (2011) Friendship and mobility: user movement in location-based social networks. In: KDD, pp 1082–1090
Conte A, Firmani D, Mordente C, Patrignani M, Torlone R (2017) Fast enumeration of large k-plexes. In: KDD, pp 115–124
citation_journal_title=Adv Phys; citation_title=Analyzing and modeling real-world phenomena with complex networks: a survey of applications; citation_author=L da Fontoura Costa, ON Oliveira, G Travieso, FA Rodrigues, PR Villas Boas, L Antiqueira, MP Viana, LE Correa Rocha; citation_volume=60; citation_issue=3; citation_publication_date=2011; citation_pages=329-412; citation_doi=10.1080/00018732.2011.572452; citation_id=CR10
Cui W, Xiao Y, Wang H, Wang W (2014) Local search of communities in large graphs. In: SIGMOD, pp 991–1002
citation_journal_title=PVLDB; citation_title=Effective community search for large attributed graphs; citation_author=Y Fang, R Cheng, S Luo, J Hu; citation_volume=9; citation_issue=12; citation_publication_date=2016; citation_pages=1233-1244; citation_id=CR12
citation_journal_title=SIAM J Comput; citation_title=A fast parametric maximum flow algorithm and applications; citation_author=G Gallo, MD Grigoriadis, RE Tarjan; citation_volume=18; citation_issue=1; citation_publication_date=1989; citation_pages=30-55; citation_doi=10.1137/0218003; citation_id=CR13
Giatsidis C, Thilikos DM, Vazirgiannis M (2011) D-cores: measuring collaboration of directed graphs based on degeneracy. In: ICDM, pp 201–210
Giatsidis C, Thilikos DM, Vazirgiannis M (2011) Evaluating cooperation in communities with the k-core structure. In: ASONAM, pp 87–93
citation_journal_title=Random Struct Algorithms; citation_title=A simple solution to the k-core problem; citation_author=S Janson, MJ Luczak; citation_volume=30; citation_issue=1–2; citation_publication_date=2007; citation_pages=50-62; citation_doi=10.1002/rsa.20147; citation_id=CR16
citation_journal_title=PVLDB; citation_title=K-core decomposition of large networks on a single pc; citation_author=W Khaouid, M Barsky, V Srinivasan, A Thomo; citation_volume=9; citation_issue=1; citation_publication_date=2015; citation_pages=13-23; citation_id=CR17
citation_journal_title=TKDD; citation_title=Graph evolution: densification and shrinking diameters; citation_author=J Leskovec, J Kleinberg, C Faloutsos; citation_volume=1; citation_issue=1; citation_publication_date=2007; citation_pages=2; citation_doi=10.1145/1217299.1217301; citation_id=CR18
citation_journal_title=PVLDB; citation_title=Influential community search in large networks; citation_author=R-H Li, L Qin, JX Yu, R Mao; citation_volume=8; citation_issue=5; citation_publication_date=2015; citation_pages=509-520; citation_id=CR19
citation_journal_title=TKDE; citation_title=Efficient core maintenance in large dynamic graphs; citation_author=R-H Li, JX Yu, R Mao; citation_volume=26; citation_issue=10; citation_publication_date=2014; citation_pages=2453-2465; citation_id=CR20
citation_journal_title=Discrete Math; citation_title=Size and connectivity of the k-core of a random graph; citation_author=T Łuczak; citation_volume=91; citation_issue=1; citation_publication_date=1991; citation_pages=61-68; citation_doi=10.1016/0012-365X(91)90162-U; citation_id=CR21
Ma H, Zhou D, Liu C, Lyu MR, King I (2011) Recommender systems with social regularization. In: Proceedings of the fourth ACM international conference on Web search and data mining, pp 287–296
Massa P, Avesani P (2007) Trust-aware recommender systems. In: RecSys, pp 17–24
citation_journal_title=Random Struct Algorithms; citation_title=Cores in random hypergraphs and boolean formulas; citation_author=M Molloy; citation_volume=27; citation_issue=1; citation_publication_date=2005; citation_pages=124-135; citation_doi=10.1002/rsa.20061; citation_id=CR24
citation_journal_title=TPDS; citation_title=Distributed k-core decomposition; citation_author=A Montresor, F De Pellegrini, D Miorandi; citation_volume=24; citation_issue=2; citation_publication_date=2013; citation_pages=288-300; citation_id=CR25
OBrien MP, Sullivan BD (2014) Locally estimating core numbers. In: ICDM, pp 460–469
citation_journal_title=J Combin Theory Ser B; citation_title=Sudden emergence of a giantk-core in a random graph; citation_author=B Pittel, J Spencer, N Wormald; citation_volume=67; citation_issue=1; citation_publication_date=1996; citation_pages=111-151; citation_doi=10.1006/jctb.1996.0036; citation_id=CR27
citation_journal_title=PVLDB; citation_title=Streaming algorithms for k-core decomposition; citation_author=AE Saríyüce, B Gedik, G Jacques-Silva, K-L Wu, ÜV Çatalyürek; citation_volume=6; citation_issue=6; citation_publication_date=2013; citation_pages=433-444; citation_id=CR28
citation_journal_title=Soc Netw; citation_title=Network structure and minimum degree; citation_author=SB Seidman; citation_volume=5; citation_issue=3; citation_publication_date=1983; citation_pages=269-287; citation_doi=10.1016/0378-8733(83)90028-X; citation_id=CR29
Tang J, Zhang J, Yao L, Li J, Zhang L, Su Z (2008) Arnetminer: extraction and mining of academic social networks. In: KDD, pp 990–998
citation_journal_title=PVLDB; citation_title=Truss decomposition in massive networks; citation_author=J Wang, J Cheng; citation_volume=5; citation_issue=9; citation_publication_date=2012; citation_pages=812-823; citation_id=CR31
Wen D, Qin L, Zhang Y, Lin X, Yu JX (2016) I/o efficient core graph decomposition at web scale. In: ICDE, pp 133–144. IEEE
Wu Y, Jin R, Zhu X, Zhang X (2015) Finding dense and connected subgraphs in dual networks. In: ICDE, pp 915–926
citation_title=K-connected cores computation in large dual networks; citation_inbook_title=Database systems for advanced applications; citation_publication_date=2018; citation_pages=169-186; citation_id=CR34; citation_author=L Yue; citation_author=D Wen; citation_author=L Cui; citation_author=L Qin; citation_author=Y Zheng; citation_publisher=Springer