SYSTEM, METHOD, AND RECORDING MEDIUM FOR EFFICIENT COHESIVE SUBGRAPH IDENTIFICATION IN ENTITY COLLECTIONS FOR INLIER AND OUTLIER DETECTION

• US 20170076178A1
• Filed: 09/14/2015
• Published: 03/16/2017
• Est. Priority Date: 09/14/2015
• Status: Active Grant

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Cheng, Yu, Pankanti, Sharathchandra U., Ratha, Nalini K.
• Granted Patent: US 9,852,359 B2
• Time in Patent Office: Days
• US Class Current: 1/1
• CPC Class Codes: G06F 18/22 Matching criteria, e.g. proximity measures
• CPC Class Codes: G06F 18/23 Clustering techniques
• CPC Class Codes: G06F 18/29 Graphical models, e.g. Bayesian networks
• CPC Class Codes: G06V 10/84 using probabilistic graphical models from image or video features, e.g. Markov models or Bayesian networks
• CPC Class Codes: G06V 20/30 in albums, collections or shared content, e.g. social network photos or video
• CPC Class Codes: G06V 40/161 Detection; Localisation; Normalisation

Abstract

A similarity detection system receiving a plurality of input entities, the system including a cohesive subgraph identification device configured to calculate, based on attributes of the plurality of input entities, a first parameter and a second parameter based on the first parameter, and further configured to identify a plurality of subgraphs from the second parameter and a subgraph correlation tracking and clustering device configured to determine a relationship between different subgraphs based on a similarity factor between the second parameter and the plurality of subgraphs.

Claims

1. A similarity detection system receiving a plurality of input entities, the system comprising:

a cohesive subgraph identification device configured to calculate, based on attributes of the plurality of input entities, a first parameter and a second parameter based on the first parameter, and further configured to identify a plurality of subgraphs from the second parameter; and

a subgraph correlation tracking and clustering device configured to determine a relationship between different subgraphs based on a similarity factor between the second parameter and the plurality of subgraphs.

2. The similarity detection system according to claim 1, wherein the subgraph correlation tracking and clustering device is further configured to combine the different subgraphs based on the similarity factor between the second parameter and the plurality of subgraphs.

3. The similarity detection system according to claim 1, wherein the first parameter includes k-cores and the second parameter includes (k, d)-cores.

4. The similarity detection system according to claim 1, wherein the plurality of input entities comprise a list of images.

5. The similarity detection system according to claim 1, wherein the subgraph correlation tracking and clustering device is further configured to output outliers that include the subgraphs not combined by the subgraph correlation tracking and clustering device.

6. The similarity detection system according to claim 1, wherein the subgraph correlation tracking and clustering device is further configured to output inliers that include the subgraphs combined by the subgraph correlation tracking and clustering device.

7. The similarity detection system according to claim 1, wherein the attributes comprise a mathematical representation of the entities.

8. The similarity detection system according to claim 1, wherein the second parameter includes an additional factor to control a strength of the similarity factor between entities than the first parameter.

9. The similarity detection system according to claim 1, wherein the cohesive subgraph identification device calculates the second parameter using either a Zigzag algorithm or a NodeFirst algorithm.

10. The similarity detection system according to claim 3, wherein the (k, d)-cores include a cohesive internal structure enhanced by at least d common neighbors as witnesses of commonality between nodes connected by each edge than the k-Cores, and

wherein d is an integer greater than zero.

11. A similarity detection method, comprising:

receiving a plurality of input entities;

calculating, based on attributes of the plurality of input entities, a first parameter and a second parameter based on the first parameter;

identifying a plurality of subgraphs from the second parameter; and

determining a relationship between different subgraphs based on a similarity factor between the second parameter and the plurality of subgraphs.

12. The similarity detection method according to claim 11, further comprising combining the different subgraphs based on the similarity factor between the second parameter and the plurality of subgraphs.

13. The similarity detection method according to claim 11, wherein the first parameter includes k-cores and the second parameter includes (k, d)-cores.

14. The similarity detection method according to claim 11, wherein the plurality of input entities comprise a list of images.

15. The similarity detection method according to claim 12, further comprising outputting outliers that include the subgraphs not combined by the combining

16. A non-transitory computer-readable recording medium recording a similarity detection program, the program causing a computer to perform:

receiving a plurality of input entities;

calculating, based on attributes of the plurality of input entities, a first parameter and a second parameter based on the first parameter;

identifying a plurality of subgraphs from the second parameter; and

determining a relationship between different subgraphs based on a similarity factor between the second parameter and the plurality of subgraphs.

17. The non-transitory computer-readable recording medium according to claim 16, further comprising combining the different subgraphs based on the similarity factor between the second parameter and the plurality of subgraphs.

18. The non-transitory computer-readable recording medium according to claim 16, wherein the first parameter includes k-cores and the second parameter includes (k, d)-cores.

19. The non-transitory computer-readable recording medium according to claim 16, wherein the plurality of input entities comprise a list of images.

20. The non-transitory computer-readable recording medium according to claim 17, further comprising outputting outliers that include the subgraphs not combined by the combining.