Vi studerar problemet med upptäckt av förändringspunkter och lokalisering i dynamiska nätverk. Vi antar att vi observerar en sekvens av oberoende adjacencymatriser av given storlek, var och en motsvarar en insikt från en okänd inhomogene Bernoulli modell. Den underliggande fördelningen av adjakens matriser kan ändras över en delmängd av tidpunkterna, kallas förändringspunkter. Vår uppgift är att med hög noggrannhet återställa det okända antalet och positionerna för förändringspunkterna. Vår allmänna modellinställning gör det möjligt för alla modellparametrar att ändras med det totala antalet tidspunkter, inklusive nätverksstorleken, det minimala avståndet mellan på varandra följande förändringspunkter, storleken på den minsta förändringen och graden av gleshet i nätverken. Vi identifierar först en omöjlig region i utrymmet för modellparametrarna så att ingen förändringspunktsestimator är bevisligen konsekvent om data genereras enligt parametrar som faller i den regionen. Vi föreslår en beräkningsmässigt enkel ny algoritm för nätverksbytespunkt lokalisering, kallas Network Binary Segmentation, som bygger på viktade medelvärden av adjacency matriser. Vi visar att Network Binary Segmentation är konsekvent över en rad modellparametrar som nästan täcker komplementet till omöjlighetsregionen, vilket visar förekomsten av en fasövergång för det aktuella problemet. Därefter utformar vi en mer sofistikerad algoritm baserad på singular value thinding, kallad Local Raffination, som ger mer exakta uppskattningar av bytespunktens placeringar. Vi visar att, under lämpliga förhållanden, lokala Raffinering garanterar en minimax optimal hastighet för nätverksbytespunkt lokalisering samtidigt som den förblir beräkningsbart genomförbar.
I REF studeras också problemet med detektering av förändringspunkter i dynamiska nätverk och de ger rigorösa teoretiska resultat.
Optimal Change Point Detection and Localization in Sparse Dynamic Networks
{'venue': None, 'journal': 'arXiv: Methodology', 'mag_field_of_study': ['Mathematics']}