| 399 | // ---------------------------------------------------------------------------------------- |
| 400 | |
| 401 | inline double modularity ( |
| 402 | const std::vector<sample_pair>& edges, |
| 403 | const std::vector<unsigned long>& labels |
| 404 | ) |
| 405 | { |
| 406 | const unsigned long num_nodes = max_index_plus_one(edges); |
| 407 | // make sure requires clause is not broken |
| 408 | DLIB_ASSERT(labels.size() == num_nodes, |
| 409 | "\t double modularity()" |
| 410 | << "\n\t Invalid inputs were given to this function" |
| 411 | ); |
| 412 | |
| 413 | unsigned long num_labels; |
| 414 | const std::vector<unsigned long>& labels_ = dlib::impl::remap_labels(labels,num_labels); |
| 415 | |
| 416 | std::vector<double> cluster_sums(num_labels,0); |
| 417 | std::vector<double> k(num_nodes,0); |
| 418 | |
| 419 | double Q = 0; |
| 420 | double m = 0; |
| 421 | for (unsigned long i = 0; i < edges.size(); ++i) |
| 422 | { |
| 423 | const unsigned long n1 = edges[i].index1(); |
| 424 | const unsigned long n2 = edges[i].index2(); |
| 425 | k[n1] += edges[i].distance(); |
| 426 | if (n1 != n2) |
| 427 | k[n2] += edges[i].distance(); |
| 428 | |
| 429 | if (n1 != n2) |
| 430 | m += edges[i].distance(); |
| 431 | else |
| 432 | m += edges[i].distance()/2; |
| 433 | |
| 434 | if (labels_[n1] == labels_[n2]) |
| 435 | { |
| 436 | if (n1 != n2) |
| 437 | Q += 2*edges[i].distance(); |
| 438 | else |
| 439 | Q += edges[i].distance(); |
| 440 | } |
| 441 | } |
| 442 | |
| 443 | if (m == 0) |
| 444 | return 0; |
| 445 | |
| 446 | for (unsigned long i = 0; i < labels_.size(); ++i) |
| 447 | { |
| 448 | cluster_sums[labels_[i]] += k[i]; |
| 449 | } |
| 450 | |
| 451 | for (unsigned long i = 0; i < labels_.size(); ++i) |
| 452 | { |
| 453 | Q -= k[i]*cluster_sums[labels_[i]]/(2*m); |
| 454 | } |
| 455 | |
| 456 | return 1.0/(2*m)*Q; |
| 457 | } |
| 458 | |