Scalable Algorithms for Data and Network Analysis
A Big Data korában a hatékony algoritmusokra nagyobb szükség van, mint valaha. Miközben a Big Data az úttörők által elképzelt aszimptotikus világba vezet minket, a hatékony algoritmusok klasszikus fogalmát is megkérdőjelezi: Az algoritmusok, amelyek korábban a polinomiális idejű jellemzés szerint hatékonyaknak számítottak, már nem biztos, hogy megfelelőek a mai problémák megoldására.
Nemcsak kívánatos, hanem elengedhetetlen, hogy a hatékony algoritmusok skálázhatók legyenek. Más szóval, a komplexitásuknak közel lineárisnak vagy szublineárisnak kell lennie a probléma méretéhez képest. Így a skálázhatóságot, és nem csak a polinomiális idejű kiszámíthatóságot kell a hatékony számítás jellemzésének központi komplexitási fogalmává emelni.
A Scalable Algorithms for Data and Network Analysis a skálázható algoritmusok tervezéséhez szükséges algoritmikus technikák egy családját vizsgálja. Ezek a technikák közé tartozik a helyi hálózatfeltárás, a fejlett mintavételezés, a ritkítás és a geometriai partícionálás.
Ide tartoznak a spektrális gráfelméleti módszerek is, mint például az elektromos áramlások kiszámításához és a Gauss Markov-véletlenmezőkből történő mintavételezéshez használtak. Ezek a módszerek jól példázzák a kombinatorikus, numerikus és statisztikai gondolkodásmód ötvözését a hálózatelemzésben.
A Scalable Algorithms for Data and Network Analysis (Skálázható algoritmusok adat- és hálózatelemzéshez) című könyv néhány alapvető problémán keresztül mutatja be e technikák használatát, amelyek alapvető fontosságúak a hálózati adatok elemzésében, különösen a jelentős csomópontok és összefüggő klaszterek/közösségek azonosítása szempontjából a társadalmi és információs hálózatokban. Emellett tárgyal néhány, a gráfelméleti modelleken túli keretet is a hálózatelemzésben és a társadalmi hatásokban felmerülő fogalmi kérdések tanulmányozására.