Large informatics graphs such as large social and information networks that are increasingly-common in Internet applications have numerous subtle and deeply counterintuitive properties. For example, whereas people usually think of the data as consisting of some "global" structure (low-rank, low-rank plus sparse, hierarchical, etc.), which is then corrupted by some noise, perhaps the simplest and most correct description of the large-scale empirical structure of most large social and information networks is that it consists of an empirically-quasirandom scaffolding, upon which little "local" pockets of structure (which are the structures of interest in most applications) sit. What that claim precisely means, how one can empirically test and validate it in a rigorous way, and it's implications for large-scale network analysis and large-scale data analysis more generally will be discussed.
Copyright. All Rights Reserved.