Systems and methods for evaluating a group detection tool

• US 7,890,440 B1
• Filed: 08/29/2006
• Issued: 02/15/2011
• Est. Priority Date: 08/29/2006
• Status: Expired due to Fees

• Current Assignee: Leidos, Inc. (Leidos Holdings, Inc.)
• Original Assignee: Science Applications International Corporation
• Inventors: Hardy, William Christopher
• Primary Examiner(s): VINCENT, DAVID ROBERT
• Application Number:
  US11/511,764
• Time in Patent Office: 1,631 Days
• Field of Search: 706 2045- 47, 706/62, 705/319, 707/727, 707/728, 707/737, 707/739, 707/748
• US Class Current: 706/20
• CPC Class Codes: G06F 18/00 Pattern recognition
• CPC Class Codes: G06F 18/217 Validation; Performance evaluation; Active pattern learning techniques
• CPC Class Codes: G06F 18/232 Non-hierarchical techniques
• CPC Class Codes: G06Q 30/02 Marketing; Price estimation or determination; Fundraising

Abstract

Systems and methods for evaluating a group detection tool are described. One described method includes a set of data including a collection of asserted links between pairs of individuals, creating a sorted list of the individuals present in the collection of asserted links, and creating a square co-occurrence matrix describing the collection of asserted links, the square co-occurrence matrix including a plurality of rows and a plurality of columns each containing the sorted list of individuals. The method also includes inserting a link indicator in each cell of the square co-occurrence matrix, the link indicator having a first value if a first individual associated with the row and a second individual associated with the column are linked and a second value if they are not, identifying a plurality of square sub-co-occurrence matrices in the square co-occurrence matrix, generating a statistic for a characteristic of at least one class of the plurality of square sub-co-occurrence matrices, and identifying one of the plurality of sub-co-occurrence matrices for each of the at least one class of square sub-co-occurrence matrices. The method further includes evaluating the performance of the group detection tool by: applying the group detection tool to the set of data, and determining the extent to which a plurality of individuals in the at least one square sub-co-occurrence matrix are associated in one or more groups generated by the group detection tool.

Claims

1. A method of evaluating a group detection tool without knowledge regarding a composition of real-world groups to which individuals in an observed population belong, comprising:

receiving, using a microprocessor, a set of data comprising a collection of asserted links between pairs of individuals;

creating, using the microprocessor, a list of the individuals present in the collection of asserted links, each individual on the list being assigned a unique numerical identifier;

creating, using the microprocessor, a square co-occurrence matrix describing the collection of asserted links, the square co-occurrence matrix comprising a plurality of rows and a plurality of columns each containing the list of individuals;

inserting, using the microprocessor, a link indicator in each cell of the square co-occurrence matrix, the link indicator having a first value if a first individual associated with the row and a second individual associated with the column are linked and a second value if they are not;

identifying, using the microprocessor, a plurality of square sub-co-occurrence matrices in the square co-occurrence matrix;

generating, using the microprocessor, a statistic for a characteristic of at least one class of the plurality of square sub-co-occurrence matrices;

identifying, using the microprocessor, one of the plurality of sub-co-occurrence matrices for each of the at least one class of square sub-co-occurrence matrices; and

evaluating, using the microprocessor, the performance of the group detection tool by;

applying the group detection tool to the set of data, and

determining the extent to which a plurality of individuals in the at least one square sub-co-occurrence matrix are associated in one or more groups generated by the group detection tool.

2. The method of claim 1, further comprising determining a link between a pair of individuals, the link implying both the ability and likelihood of exchange of information between the pair of individuals.

3. The method of claim 1, wherein the class of sub-co-occurrence matrices comprises square a plurality of sub-co-occurrence matrices of size N×

N for at least one value of N greater than 3.

4. The method of claim 3, wherein the statistic for each of the at least one class of sub-co-occurrence matrices is the sum of link indicators having the first value in each of the columns of the sub-co-occurrence matrices in the class.

5. The method of claim 4, further comprising determining that a pair of individuals is associated if the sum of the link indicators having the first value exceeds a threshold value.

6. The method of claim 5, wherein the threshold value comprises a first threshold value and further comprising determining the first threshold value having a probability of occurrence less than a second threshold value.

7. The method of claim 5, further comprising determining the threshold value by:

determining a first sum of link indicators in sub-co-occurrence matrices having fewer elements than in the sub-co-occurrence matrix;

determining a second sum of link indicators in sub-co-occurrence matrices having more elements than in the sub-co-occurrence matrix; and

setting the threshold value between the first sum and the second sum.

8. The method of claim 5, further comprising creating a candidate cluster set comprising all pairs of individuals for which the sum of the link indicators having the first value exceeds the threshold value.

9. The method of claim 8, further comprising adjusting the candidate cluster set.

10. The method of claim 9, wherein adjusting the candidate cluster set comprises removing any clusters comprising 3 or fewer members from the candidate cluster set.

11. The method of claim 9, wherein adjusting the candidate cluster set comprises removing aggregate clusters from the candidate cluster set.

12. The method of claim 1, wherein the at least one class comprises a plurality of classes of the same size.

13. The method of claim 12, wherein the statistic comprises the sum of link indicators having the second value in each of the columns of the sub-co-occurrence matrices in the class.

14. The method of claim 13, further comprising creating of a candidate cluster set comprising all pairs of individuals for which the sum of the link indicators having the second value is below a threshold value.

15. The method of claim 14, wherein the threshold value is 0.

16. The method of claim 1, wherein the first value comprises a “

1” and

the second value comprises a “

0.”

17. The method of claim 1, wherein the link indicator comprises the first value if the first individual and the second individual are the same.

18. A non-transitory computer-readable storage medium with an executable program stored thereon, wherein the program instructs a microprocessor to perform the following steps for evaluating a group detection tool without knowledge regarding a composition of real-world groups to which individuals in an observed population belong:

receiving a set of data comprising a collection of asserted links between pairs of individuals;

creating a list of the individuals present in the collection of asserted links, each individual on the list being assigned a unique numerical identifier

creating a square co-occurrence matrix describing the collection of asserted links, the square co-occurrence matrix comprising a plurality of rows and a plurality of columns each containing the list of individuals;

inserting a link indicator in each cell of the square co-occurrence matrix, the link indicator having a first value if a first individual associated with the row and a second individual associated with the column are linked and a second value if they are not;

identifying a plurality of square sub-co-occurrence matrices in the square co-occurrence matrix;

generating a statistic for a characteristic of at least one class of the plurality of square sub-co-occurrence matrices;

identifying one of the plurality of sub-co-occurrence matrices for each of the at least one class of square sub-co-occurrence matrices; and

evaluating the performance of the group detection tool by;

applying the group detection tool to the set of data, and

determining the extent to which a plurality of individuals in the at least one square sub-co-occurrence matrix are associated in one or more groups generated by the group detection tool.

19. The non-transitory computer-readable storage medium of claim 18, further comprising program code for determining a link between a pair of individuals, the link implying both the ability and likelihood of exchange of information between the pair of individuals.

20. The non-transitory computer-readable storage medium of claim 18, wherein the class of sub-co-occurrence matrices comprises square a plurality of sub-co-occurrence matrices of size N×

N for at least one value of N greater than 3.

21. The non-transitory computer-readable storage medium of claim 20, wherein the statistic for each of the at least one class of sub-co-occurrence matrices is the sum of link indicators having the first value in each of the columns of the sub-co-occurrence matrices in the class.

22. The non-transitory computer-readable storage medium of claim 21, further comprising program code for determining that a pair of individuals is associated if the sum of the link indicators having the first value exceeds a threshold value.

23. The non-transitory computer-readable storage medium of claim 22, further comprising program code for determining the threshold value by:

determining a first sum of link indicators in sub-co-occurrence matrices having fewer elements than in the sub-co-occurrence matrix;

determining a second sum of link indicators in sub-co-occurrence matrices having more elements than in the sub-co-occurrence matrix; and

setting the threshold value between the first sum and the second sum.

24. The non-transitory computer-readable storage medium of claim 22, further comprising program code for creating a candidate cluster set comprising all pairs of individuals for which the sum of the link indicators having the first value exceeds the threshold value.

25. The non-transitory computer-readable storage medium of claim 24, further comprising program code for adjusting the candidate cluster set.

26. The non-transitory computer-readable storage medium of claim 24, wherein program code for adjusting the candidate cluster set comprises program code for removing any clusters comprising 3 or fewer members from the candidate cluster set.

27. The non-transitory computer-readable storage medium of claim 25, wherein program code for adjusting the candidate cluster set comprises program code for removing aggregate clusters from the candidate cluster set.

28. The non-transitory computer-readable storage medium of claim 18, wherein the at least one class comprises a plurality of classes of the same size.

29. The non-transitory computer-readable storage medium of claim 28, wherein the statistic comprises the sum of link indicators having the second value in each of the columns of the sub-co-occurrence matrices in the class.

30. The non-transitory computer-readable storage medium of claim 29, further comprising program code for creating a candidate cluster set comprising all pairs of individuals for which the sum of the link indicators having the second value is below a threshold value.