{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,17]],"date-time":"2025-10-17T13:29:30Z","timestamp":1760707770435,"version":"3.41.0"},"reference-count":18,"publisher":"Association for Computing Machinery (ACM)","issue":"2","license":[{"start":{"date-parts":[[2005,12,1]],"date-time":"2005-12-01T00:00:00Z","timestamp":1133395200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["SIGKDD Explor. Newsl."],"published-print":{"date-parts":[[2005,12]]},"abstract":"<jats:p>Many real applications can be modeled using bipartite graphs, such as users vs. files in a P2P system, traders vs. stocks in a financial trading system, conferences vs. authors in a scientific publication network, and so on. We introduce two operations on bipartite graphs: 1) identifying similar nodes (relevance search), and 2) finding nodes connecting irrelevant nodes (anomaly detection). And we propose algorithms to compute the relevance score for each node using random walk with restarts and graph partitioning; we also propose algorithms to identify anomalies, using relevance scores. We evaluate the quality of relevance search based on semantics of the datasets, and we also measure the performance of the anomaly detection algorithm with manually injected anomalies. Both effectiveness and efficiency of the methods are confirmed by experiments on several real datasets.<\/jats:p>","DOI":"10.1145\/1117454.1117461","type":"journal-article","created":{"date-parts":[[2007,1,17]],"date-time":"2007-01-17T18:32:02Z","timestamp":1169058722000},"page":"48-55","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":47,"title":["Relevance search and anomaly detection in bipartite graphs"],"prefix":"10.1145","volume":"7","author":[{"given":"Jimeng","family":"Sun","sequence":"first","affiliation":[{"name":"Carnegie Mellon Univ."}]},{"given":"Huiming","family":"Qu","sequence":"additional","affiliation":[{"name":"Univ. of Pittsburgh"}]},{"given":"Deepayan","family":"Chakrabarti","sequence":"additional","affiliation":[{"name":"Yahoo! Research"}]},{"given":"Christos","family":"Faloutsos","sequence":"additional","affiliation":[{"name":"Univ. of Pittsburgh"}]}],"member":"320","published-online":{"date-parts":[[2005,12]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1145\/376284.375668"},{"volume-title":"UAI","year":"1998","author":"Breese J.","key":"e_1_2_1_2_1"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0169-7552(98)00110-X"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.5555\/1053072.1053085"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/1014052.1014064"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/956750.956764"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/347090.347121"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1073\/pnas.122653799"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/511446.511513"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/775047.775126"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.5555\/795666.796585"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1006\/jpdc.1997.1404"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.5555\/2384225.2384261"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/956750.956831"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/1014052.1014135"},{"volume-title":"Addison-Wesley","year":"1999","author":"Ribeiro-Neto Berthier","key":"e_1_2_1_17_1"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/223904.223931"},{"key":"e_1_2_1_19_1","unstructured":"Gilbert Strang. Introduction to Linear Algebra. Wellesley-Cambridge Press 3 edition 1998.  Gilbert Strang. Introduction to Linear Algebra. Wellesley-Cambridge Press 3 edition 1998."}],"container-title":["ACM SIGKDD Explorations Newsletter"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1117454.1117461","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/1117454.1117461","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T16:18:45Z","timestamp":1750263525000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1117454.1117461"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2005,12]]},"references-count":18,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2005,12]]}},"alternative-id":["10.1145\/1117454.1117461"],"URL":"https:\/\/doi.org\/10.1145\/1117454.1117461","relation":{},"ISSN":["1931-0145","1931-0153"],"issn-type":[{"type":"print","value":"1931-0145"},{"type":"electronic","value":"1931-0153"}],"subject":[],"published":{"date-parts":[[2005,12]]},"assertion":[{"value":"2005-12-01","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}