Class Discussions 2/24/10
4.2 Finding Cliques – any subset of vertices in an undirected graph in which every two vertices are connected by a single edge and no edges or vertices. Brute Force algorithm: Time needed to compute maximal clique is exponential. Only feasible if number of vertices is constant.
4.3 Random Graphs – a graph of randomly placed edges. Average vertex degree is (n – 1)/p -> np. Random graphs are not adequate models for real-life networks due to a high tendency of clustering. These networks also tend to have right-skewed degree distributions that follow a power law, with a few massive outlying events.
4.4 Scale-Free Graphs – Degree distribution follows power law. Barabasi-Albert algorithm generates scale free networks. A node is more likely to receive additional links if already highly connected. Considered ultra small world. Party hubs interactwith most partners simultaneously, date hubs bind to partners at specific times.
