2014 · 45 citations · 32 references
ComputingComputer ScienceMathematicsAlgorithmsCombinatoricsTheory Of ComputationAlgorithm AnalysisGeometric GraphsGraph AlgorithmsHeuristic OptimizationRandomized Geometric AlgorithmsSublinear AlgorithmsEnumeration Algorithms For GraphsGraph EnumerationHeuristicsScalable Graph AlgorithmsWorst-case Complexity
Triangle enumeration is a fundamental graph operation. Despite the lack of provably efficient (linear, or slightly super-linear) worst-case algorithms for this problem, practitioners run simple, efficient heuristics to find all triangles in graphs with millions of vertices. How are these heuristics exploiting the structure of these special graphs to provide major speedups in running time?
32
Collective dynamics of ‘small-world’ networks
Duncan J. Watts, Steven H. Strogatz · Nature · 1998 · 43.2K citations
Emergence of Scaling in Random Networks
Albert-Ĺaszló Barabási, Réka Albert · Science · 1999 · 36.4K citations · Full text
Social Capital in the Creation of Human Capital
James S. Coleman · American Journal of Sociology · 1988 · 25.4K citations
The Structure and Function of Complex Networks
Michael Newman · SIAM Review · 2003 · 18.7K citations · Full text