{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,12,12]],"date-time":"2025-12-12T13:04:33Z","timestamp":1765544673071,"version":"3.41.0"},"publisher-location":"New York, New York, USA","reference-count":50,"publisher":"ACM Press","license":[{"start":{"date-parts":[[2018,1,1]],"date-time":"2018-01-01T00:00:00Z","timestamp":1514764800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"name":"Army Research Lab","award":["W911NF-09-2-0053"],"award-info":[{"award-number":["W911NF-09-2-0053"]}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2018]]},"DOI":"10.1145\/3178876.3186118","type":"proceedings-article","created":{"date-parts":[[2018,4,13]],"date-time":"2018-04-13T15:53:48Z","timestamp":1523634828000},"page":"519-528","source":"Crossref","is-referenced-by-count":7,"title":["Spectral Algorithms for Temporal Graph Cuts"],"prefix":"10.1145","author":[{"given":"Arlei","family":"Silva","sequence":"first","affiliation":[{"name":"University of California, Santa Barbara, Santa Barbara, CA, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Ambuj","family":"Singh","sequence":"additional","affiliation":[{"name":"University of California, Santa Barbara, Santa Barbara, CA, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Ananthram","family":"Swami","sequence":"additional","affiliation":[{"name":"Army Research Laboratory, Adelphi, MD, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","reference":[{"key":"key-10.1145\/3178876.3186118-1","doi-asserted-by":"crossref","unstructured":"William Anderson Jr and Thomas Morley . 1985. Eigenvalues of the Laplacian of a graph. Linear and multilinear algebra Vol. 18, 2 (1985), 141--145.","DOI":"10.1080\/03081088508817681"},{"key":"key-10.1145\/3178876.3186118-2","doi-asserted-by":"crossref","unstructured":"Sanjeev Arora, Satish Rao, and Umesh Vazirani . 2009. Expander flows, geometric embeddings and graph partitioning. J. ACM Vol. 56, 2 (2009), 5.","DOI":"10.1145\/1502793.1502794"},{"key":"key-10.1145\/3178876.3186118-3","doi-asserted-by":"crossref","unstructured":"Lars Backstrom, Dan Huttenlocher, Jon Kleinberg, and Xiangyang Lan . 2006. Group formation in large social networks: membership, growth, and evolution KDD. ACM, New York, NY, USA, 44--54.","DOI":"10.1145\/1150402.1150412"},{"key":"key-10.1145\/3178876.3186118-4","doi-asserted-by":"crossref","unstructured":"Marya Bazzi, Mason A Porter, Stacy Williams, Mark McDonald, Daniel J Fenn, and Sam D Howison . 2016. Community detection in temporal multilayer networks, with an application to correlation networks. Multiscale Modeling & Simulation Vol. 14, 1 (2016), 1--41.","DOI":"10.1137\/15M1009615"},{"key":"key-10.1145\/3178876.3186118-5","doi-asserted-by":"crossref","unstructured":"Steffen Bickel and Tobias Scheffer . 2004. Multi-view clustering.. In ICDM. IEEE, Washington, DC, USA, 19--26.","DOI":"10.1109\/ICDM.2004.10095"},{"key":"key-10.1145\/3178876.3186118-6","unstructured":"Michael M Bronstein, Joan Bruna, Yann LeCun, Arthur Szlam, and Pierre Vandergheynst . 2017. Geometric deep learning: going beyond euclidean data. IEEE Signal Processing Magazine Vol. 34, 4 (2017), 18--42."},{"key":"key-10.1145\/3178876.3186118-7","doi-asserted-by":"crossref","unstructured":"Moses Charikar, Chandra Chekuri, Tomás Feder, and Rajeev Motwani . 2004. Incremental clustering and dynamic information retrieval. SIAM J. Comput. Vol. 33, 6 (2004), 1417--1440.","DOI":"10.1137\/S0097539702418498"},{"key":"key-10.1145\/3178876.3186118-8","unstructured":"Yun Chi, Xiaodan Song, Dengyong Zhou, Koji Hino, and Belle L Tseng . 2007. Evolutionary spectral clustering by incorporating temporal smoothness KDD. ACM, New York, NY, USA, 153--162."},{"key":"key-10.1145\/3178876.3186118-9","unstructured":"Fan RK Chung . 1997. Spectral graph theory. American Mathematical Society, Providence, RI, USA."},{"key":"key-10.1145\/3178876.3186118-10","unstructured":"Mihai Cucuringu, Ioannis Koutis, Sanjay Chawla, Gary Miller, and Richard Peng . 2016. Simple and Scalable Constrained Clustering: a Generalized Spectral Method AISTATS. PMLR, Cadiz, Spain, 445--454."},{"key":"key-10.1145\/3178876.3186118-11","doi-asserted-by":"crossref","unstructured":"JJM Cuppen . 1980. A divide and conquer method for the symmetric tridiagonal eigenproblem. Numer. Math. Vol. 36, 2 (1980), 177--195.","DOI":"10.1007\/BF01396757"},{"key":"key-10.1145\/3178876.3186118-12","doi-asserted-by":"crossref","unstructured":"Thomas Erlebach, Michael Hoffmann, and Frank Kammer . 2015. On temporal graph exploration. In ICALP. Springer, Berlin, Heidelberg, 444--455.","DOI":"10.1007\/978-3-662-47672-7_36"},{"key":"key-10.1145\/3178876.3186118-13","unstructured":"Daniel Figueiredo, Philippe Nain, Bruno Ribeiro, Edmundo de Souza e Silva, and Don Towsley . 2012. Characterizing continuous time random walks on time varying graphs SIGMETRICS. ACM, New York, NY, USA, 307--318."},{"key":"key-10.1145\/3178876.3186118-14","unstructured":"Wilfried N Gansterer, Robert C Ward, Richard P Muller, and William A Goddard III . 2003. Computing approximate eigenpairs of symmetric block tridiagonal matrices. SIAM Journal on Scientific Computing Vol. 25, 1 (2003), 65--85."},{"key":"key-10.1145\/3178876.3186118-15","unstructured":"Matan Gavish, Boaz Nadler, and Ronald Coifman . 2010. Multiscale Wavelets on Trees, Graphs and High Dimensional Data: Theory and Applications to Semi Supervised Learning.. In ICML. Omnipress, USA, 367--374."},{"key":"key-10.1145\/3178876.3186118-16","unstructured":"Gene H Golub and Charles F Van Loan . 2012. Matrix computations. Vol. Vol. 3. JHU Press, Baltimore, MD, USA."},{"key":"key-10.1145\/3178876.3186118-17","doi-asserted-by":"crossref","unstructured":"Sergio Gomez, Albert Diaz-Guilera, Jesus Gomez-Gardenes, Conrad J Perez-Vicente, Yamir Moreno, and Alex Arenas . 2013. Diffusion dynamics on multiplex networks. Physical review letters Vol. 110, 2 (2013), 028701.","DOI":"10.1103\/PhysRevLett.110.028701"},{"key":"key-10.1145\/3178876.3186118-18","doi-asserted-by":"crossref","unstructured":"Lars Hagen and Andrew B Kahng . 1992. New spectral methods for ratio cut partitioning and clustering. IEEE Transactions on Computer-aided Design of Integrated Circuits and Systems, Vol. 11, 9 (1992), 1074--1085.","DOI":"10.1109\/43.159993"},{"key":"key-10.1145\/3178876.3186118-19","doi-asserted-by":"crossref","unstructured":"Christopher J Hillar and Lek-Heng Lim . 2013. Most tensor problems are NP-hard. Journal of the ACM (JACM) Vol. 60, 6 (2013), 45.","DOI":"10.1145\/2512329"},{"key":"key-10.1145\/3178876.3186118-20","unstructured":"Roger A Horn and Charles R Johnson . 1990. Matrix analysis. Cambridge University Press, New York, NY, USA."},{"key":"key-10.1145\/3178876.3186118-21","doi-asserted-by":"crossref","unstructured":"Vikas Kawadia and Sameet Sreenivasan . 2012. Sequential detection of temporal communities by estrangement confinement. Scientific reports Vol. 2 (2012), 794--794.","DOI":"10.1038\/srep00794"},{"key":"key-10.1145\/3178876.3186118-22","unstructured":"Mikko Kivel\"a, Alex Arenas, Marc Barthelemy, James P Gleeson, Yamir Moreno, and Mason A Porter . 2014. Multilayer networks. Journal of complex networks Vol. 2, 3 (2014), 203--271."},{"key":"key-10.1145\/3178876.3186118-23","unstructured":"Ioannis Koutis, Gary Miller, and Richard Peng . 2014. A Generalized Cheeger Inequality. https:\/\/arxiv.org\/abs\/1412.6075. (2014)."},{"key":"key-10.1145\/3178876.3186118-24","unstructured":"Ioannis Koutis, Gary L. Miller, and Richard Peng . 2011. A Nearly-m Log N Time Solver for SDD Linear Systems FOCS. IEEE, Washington, DC, USA, 590--598."},{"key":"key-10.1145\/3178876.3186118-25","doi-asserted-by":"crossref","unstructured":"J Kuczy'nski and H Wo'zniakowski . 1992. Estimating the largest eigenvalue by the power and Lanczos algorithms with a random start. SIAM journal on matrix analysis and applications, Vol. 13, 4 (1992), 1094--1122.","DOI":"10.1137\/0613066"},{"key":"key-10.1145\/3178876.3186118-26","doi-asserted-by":"crossref","unstructured":"Ravi Kumar, Jasmine Novak, Prabhakar Raghavan, and Andrew Tomkins . 2005. On the bursty evolution of blogspace. World Wide Web, Vol. 8, 2 (2005), 159--178.","DOI":"10.1007\/s11280-004-4872-4"},{"key":"key-10.1145\/3178876.3186118-27","unstructured":"John Lafferty and Guy Lebanon . 2005. Diffusion Kernels on Statistical Manifolds. JMLR Vol. 6 (2005), 129--163."},{"key":"key-10.1145\/3178876.3186118-28","unstructured":"Kevin Lang . 2006. Fixing two weaknesses of the spectral method. In NIPS. MIT Press, Cambridge, MA, USA, 715--722."},{"key":"key-10.1145\/3178876.3186118-29","unstructured":"Amy N Langville and Carl D Meyer . 2011. Google's PageRank and beyond: The science of search engine rankings. Princeton University Press, Princeton, New Jersey."},{"key":"key-10.1145\/3178876.3186118-30","unstructured":"James R Lee, Shayan Oveis Gharan, and Luca Trevisan . 2014. Multiway spectral partitioning and higher-order cheeger inequalities. J. ACM Vol. 61, 6 (2014), 1--30."},{"key":"key-10.1145\/3178876.3186118-31","unstructured":"Tom Leighton and Satish Rao . 1988. An approximate max-flow min-cut theorem for uniform multicommodity flow problems with applications to approximation algorithms. FOCS. IEEE, White Plains, NY, 422--431."},{"key":"key-10.1145\/3178876.3186118-32","doi-asserted-by":"crossref","unstructured":"Jure Leskovec, Kevin J Lang, Anirban Dasgupta, and Michael W Mahoney . 2009. Community structure in large networks: Natural cluster sizes and the absence of large well-defined clusters. Internet Mathematics, Vol. 6, 1 (2009), 29--123.","DOI":"10.1080\/15427951.2009.10129177"},{"key":"key-10.1145\/3178876.3186118-33","doi-asserted-by":"crossref","unstructured":"Yifan Li, Jiawei Han, and Jiong Yang . 2004. Clustering Moving Objects. In KDD. ACM, New York, NY, USA, 617--622.","DOI":"10.1145\/1014052.1014129"},{"key":"key-10.1145\/3178876.3186118-34","doi-asserted-by":"crossref","unstructured":"Yu-Ru Lin, Yun Chi, Shenghuo Zhu, Hari Sundaram, and Belle L. Tseng . 2008. Facetnet: A Framework for Analyzing Communities and Their Evolutions in Dynamic Networks WWW. ACM, New York, NY, USA, 685--694.","DOI":"10.1145\/1367497.1367590"},{"key":"key-10.1145\/3178876.3186118-35","doi-asserted-by":"crossref","unstructured":"Anand Louis, Prasad Raghavendra, Prasad Tetali, and Santosh Vempala . 2012. Many Sparse Cuts via Higher Eigenvalues. In STOC. ACM, New York, NY, USA, 1131--1140.","DOI":"10.1145\/2213977.2214079"},{"key":"key-10.1145\/3178876.3186118-36","doi-asserted-by":"crossref","unstructured":"Othon Michail . 2016. An introduction to temporal graphs: An algorithmic perspective. Internet Mathematics, Vol. 12, 4 (2016), 239--280.","DOI":"10.1080\/15427951.2016.1177801"},{"key":"key-10.1145\/3178876.3186118-37","unstructured":"Peter J Mucha, Thomas Richardson, Kevin Macon, Mason A Porter, and Jukka-Pekka Onnela . 2010. Community structure in time-dependent, multiscale, and multiplex networks. Science, Vol. 328, 5980 (2010), 876--878."},{"key":"key-10.1145\/3178876.3186118-38","doi-asserted-by":"crossref","unstructured":"Huazhong Ning, Wei Xu, Yun Chi, Yihong Gong, and Thomas S Huang . 2010. Incremental spectral clustering by efficiently updating the eigen-system. Pattern Recognition, Vol. 43, 1 (2010), 113--127.","DOI":"10.1016\/j.patcog.2009.06.001"},{"key":"key-10.1145\/3178876.3186118-39","unstructured":"James Rosswog and Kanad Ghose . 2008. Detecting and Tracking Spatio-temporal Clusters with Adaptive History Filtering ICDMW. IEEE, Washington, DC, USA, 448--457."},{"key":"key-10.1145\/3178876.3186118-40","doi-asserted-by":"crossref","unstructured":"Jianbo Shi and Jitendra Malik . 2000. Normalized cuts and image segmentation. IEEE Transactions on Pattern Analysis and Machine Intelligence Vol. 22 (2000), 888--905.","DOI":"10.1109\/34.868688"},{"key":"key-10.1145\/3178876.3186118-41","unstructured":"David I Shuman, Sunil K Narang, Pascal Frossard, Antonio Ortega, and Pierre Vandergheynst . 2013. The emerging field of signal processing on graphs: Extending high-dimensional data analysis to networks and other irregular domains. IEEE Signal Processing Magazine Vol. 30, 3 (2013), 83--98."},{"key":"key-10.1145\/3178876.3186118-42","doi-asserted-by":"crossref","unstructured":"Arlei Silva, Xuan Hong Dang, Prithwish Basu, Ambuj Singh, and Ananthram Swami . 2016. Graph Wavelets via Sparse Cuts. In KDD. ACM, New York, NY, USA, 1175--1184.","DOI":"10.1145\/2939672.2939777"},{"key":"key-10.1145\/3178876.3186118-43","unstructured":"Arlei Silva, Ambuj Singh, and Ananthram Swami . 2017. Spectral Algorithms for Temporal Graph Cuts. http:\/\/arxiv.org\/abs\/1702.04746.pdf. (2017)."},{"key":"key-10.1145\/3178876.3186118-44","doi-asserted-by":"crossref","unstructured":"Albert Sole-Ribalta, Manlio De Domenico, Nikos E Kouvaris, Albert Diaz-Guilera, Sergio Gomez, and Alex Arenas . 2013. Spectral properties of the Laplacian of multiplex networks. Physical Review E, Vol. 88, 3 (2013), 032807.","DOI":"10.1103\/PhysRevE.88.032807"},{"key":"key-10.1145\/3178876.3186118-45","doi-asserted-by":"crossref","unstructured":"Daniel A. Spielman and Shang-Hua Teng . 2004. Nearly-linear Time Algorithms for Graph Partitioning, Graph Sparsification, and Solving Linear Systems. In STOC. ACM, New York, NY, USA, 81--90.","DOI":"10.1145\/1007352.1007372"},{"key":"key-10.1145\/3178876.3186118-46","doi-asserted-by":"crossref","unstructured":"Daniel A Spielman and Shang-Hua Teng . 2011. Spectral sparsification of graphs. SIAM J. Comput. Vol. 40, 4 (2011), 981--1025.","DOI":"10.1137\/08074489X"},{"key":"key-10.1145\/3178876.3186118-47","doi-asserted-by":"crossref","unstructured":"Juliette Stehlé, Nicolas Voirin, Alain Barrat, Ciro Cattuto, Lorenzo Isella, Jean-Franccois Pinton, Marco Quaggiotto, Wouter Van den Broeck, Corinne Régis, Bruno Lina, and others . 2011. High-resolution measurements of face-to-face contact patterns in a primary school. PloS one, Vol. 6, 8 (2011), e23176.","DOI":"10.1371\/journal.pone.0023176"},{"key":"key-10.1145\/3178876.3186118-48","doi-asserted-by":"crossref","unstructured":"Dane Taylor, Sean A Myers, Aaron Clauset, Mason A Porter, and Peter J Mucha . 2017. Eigenvector-based centrality measures for temporal networks. Multiscale Modeling & Simulation Vol. 15, 1 (2017), 537--574.","DOI":"10.1137\/16M1066142"},{"key":"key-10.1145\/3178876.3186118-49","unstructured":"Luca Trevisan . 2013. Is Cheeger-type Approximation Possible for Nonuniform Sparsest Cut? https:\/\/arxiv.org\/pdf\/1303.2730.pdf. (2013)."},{"key":"key-10.1145\/3178876.3186118-50","unstructured":"Chang Xu, Dacheng Tao, and Chao Xu . 2013. A survey on multi-view learning. https:\/\/arxiv.org\/pdf\/1304.5634.pdf. (2013)."}],"event":{"number":"2018","sponsor":["SIGWEB, ACM Special Interest Group on Hypertext, Hypermedia, and Web","IW3C2, International World Wide Web Conference Committee"],"acronym":"WWW '18","name":"the 2018 World Wide Web Conference","start":{"date-parts":[[2018,4,23]]},"location":"Lyon, France","end":{"date-parts":[[2018,4,27]]}},"container-title":["Proceedings of the 2018 World Wide Web Conference on World Wide Web - WWW '18"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3178876.3186118","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/dl.acm.org\/ft_gateway.cfm?id=3186118&ftid=1957532&dwn=1","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T02:11:28Z","timestamp":1750212688000},"score":1,"resource":{"primary":{"URL":"http:\/\/dl.acm.org\/citation.cfm?doid=3178876.3186118"}},"subtitle":[],"proceedings-subject":"World Wide Web","short-title":[],"issued":{"date-parts":[[2018]]},"references-count":50,"URL":"https:\/\/doi.org\/10.1145\/3178876.3186118","relation":{},"subject":[],"published":{"date-parts":[[2018]]}}}