Community mining based on core objects and affiliated objects

• US 7,885,960 B2
• Filed: 07/22/2003
• Issued: 02/08/2011
• Est. Priority Date: 07/22/2003
• Status: Expired due to Fees

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Ma, Wei-Ying, Zhou, Wen-Jun, Zhang, Hong-Jiang, Wen, Ji-Rong
• Primary Examiner(s): Morrison; Jay A
• Assistant Examiner(s): Ahn; Sangwoo
• Application Number:
  US10/624,759
• Publication Number:
  US 20050021531A1
• Time in Patent Office: 2,758 Days
• Field of Search: 707 1- 10, 707100-1041
• US Class Current: 707/737
• CPC Class Codes: G06F 16/951 Indexing; Web crawling techniques
• CPC Class Codes: G06F 16/954 Navigation, e.g. using categorised browsing

Abstract

In community mining based on core objects and affiliated objects, a set of core objects for a community of objects are identified from a plurality of objects. The community is expanded, based on the set of core objects, to include a set of affiliated objects. According to one aspect, a model of a community of objects is obtained by grouping a first collection of a plurality of objects into a center portion, and grouping a second collection of the plurality of objects into one or more concentric portions around the center portion. The groupings of the first and second collections of the objects are identified as the community of objects.

Claims

1. A computer-implemented method comprising:

by a computer comprising a processor;

identifying, from a plurality of objects, a set of core objects for a data structure corresponding to a community of objects by identifying one or more objects that are referenced by at least a threshold number of other objects of the plurality of objects;

expanding, based on the set of core objects, the community of objects to include a set of affiliated objects, wherein the set of core objects and the set of affiliated objects are maintained as distinct entities within the data structure;

accessing at least one element of the data structure;

assigning the set of core objects to a center portion of a user interface independent model;

assigning each affiliated object in the set of affiliated objects to a particular concentric portion around the center of the model; and

merging together a first community of a plurality of communities and a second community of the plurality of communities in response to a finding of similarity between the core objects in the first community and the core objects in the second community,

wherein identifying the set of core objects comprises;

identifying links between objects of the plurality of objects;

finding groups of objects of the plurality of objects that satisfy a link threshold; and

identifying, as a set of core objects, one or more of the groups of objects that satisfy the link threshold,

wherein the link threshold is determined by selecting a number of the plurality of objects that is at least 1 percent of the total number of objects in the plurality of objects and multiplying an amplifying frequency factor by a weight sum of all links and dividing it by the number of the plurality of objects selected.

2. The method as recited in claim 1, further comprising:

repeating the identifying and expanding for a plurality of communities of objects, wherein the objects in each community of objects are all from the plurality of objects.

3. The method as recited in claim 2, wherein the merging results in a merged community including all of the objects of the first community and the second community and having a set of core objects that includes the core objects in the first community and the core objects in the second community.

4. The method as recited in claim 2, further comprising:

merging together a first community of the plurality of communities and a second community of the plurality of communities if there is sufficient similarity between the core and affiliated objects in the first community and the core and affiliated objects in the second community.

5. The method as recited in claim 2, further comprising:

identifying a first community of the plurality of communities and a second community of the plurality of communities;

determining whether the first community and second community satisfy one or more constraints; and

merging the first community and the second community if the one or more constraints are satisfied, wherein the merging results in a merged community including all of the objects of the first community and the second community.

6. The method as recited in claim 2, wherein one of the plurality of objects is one of the set of core objects for the community of objects, and is one of the set of affiliated objects for another community of objects.

7. The method as recited in claim 2, wherein one of the plurality of objects is one of the set of core objects for multiple communities.

8. The method as recited in claim 2, wherein one of the plurality of objects is one of the set of affiliated objects for multiple communities.

9. The method as recited in claim 1, wherein expanding the data structure corresponding to the community of objects comprises:

identifying links between objects of the plurality of objects;

identifying one or more objects of the plurality of objects, wherein a link exists from each of the identified one or more objects to at least one of the core objects of the set of core objects; and

including, in the set of affiliated objects, each of the identified one or more objects.

10. The method as recited in claim 9, wherein a rank is assigned to each affiliated object in the set of objects, the affiliated object being assigned to a particular concentric portion around the center of the model in accordance with the rank of the affiliated object.

11. The method as recited in claim 9, further comprising:

ranking each affiliated object in the set of affiliated objects in accordance with the number of links from the affiliated object to core objects of the set of core objects, wherein affiliated objects having a larger number of links to core objects have higher rankings.

12. The method as recited in claim 1, wherein each of the plurality of objects comprises a document.

13. The method as recited in claim 12, further comprising:

identifying a plurality of links, wherein each link links one object to another object, and wherein each of the plurality of links represents a citation in one document to another document.

14. The method as recited in claim 1, wherein each of the plurality of objects comprises a person.

15. The method as recited in claim 14, further comprising:

identifying a plurality of links, wherein each link links one object to another object, and wherein each of the plurality of links represents a relationship of one person to another person.

16. The method as recited in claim 1, wherein each of the plurality of objects comprises a web page.

17. The method as recited in claim 16, further comprising:

identifying a plurality of links, wherein each link links one object to another object, and wherein each of the plurality of links represents a hyperlink in one web page to another web page.

18. One or more tangible computer-readable storage media having stored thereon a plurality of instructions that, when executed by one or more processors of a device, causes the one or more processors to:

identify, from a plurality of objects, a first collection of objects to be a core of a community;

identify, from the plurality of objects, a second collection of objects that are linked to the first collection of objects wherein the second collection of objects are affiliated objects,

wherein identifying the first collection of objects to be the core of the community comprises;

identifying links between objects of the plurality of objects;

finding groups of objects of the plurality of objects that satisfy a link threshold; and

identifying, as a first collection of objects, one or more of the groups of objects that satisfy the link threshold,

wherein the link threshold is determined by selecting a number of the plurality of objects that is at least 1 percent of the total number of objects in the plurality of objects and multiply an amplifying frequency factor by a weight sum of all links and dividing it by the number of the plurality of objects selected;

assign the first collection of objects to a center portion of a user interface independent model;

assign each object of the second collection of objects to a particular concentric portion around the center of the model; and

add to the community, the second collection of objects, wherein the first collection of objects and the second collection of objects are maintained as distinct entities within a data structure.

19. The one or more tangible computer-readable storage media as recited in claim 18, wherein the plurality of instructions, when executed by the one or more processors, further cause the one or more processors to:

identify, from the plurality of objects, additional first collections of objects to be cores of additional communities;

identify, from the plurality of objects, additional second collections of objects that are linked to the first collections of objects to be affiliated objects of the additional communities;

add, to the additional communities, the respective additional second collections of objects;

add, to structures corresponding to the additional communities, the respective additional second collections of objects; and

merge together a first of the communities and a second of the communities in response to a finding of similarity between the core objects in the first of the communities and the core objects in the second of the communities.

20. The one or more tangible computer-readable storage media as recited in claim 19, wherein the merge results in a merged community including all of the objects of the first of the communities and the second of the communities and having a set of core objects that includes the core objects in the first of the communities and the core objects in the second of the communities.

21. The one or more tangible computer-readable storage media as recited in claim 19, wherein the plurality of instructions, when executed by the one or more processors, further cause the one or more processors to:

merge together a first of the communities and a second of the communities if there is sufficient similarity between the core and affiliated objects in the first of the communities and the core and affiliated objects in the second of the communities.

22. The one or more tangible computer-readable storage media as recited in claim 19, wherein the link threshold comprises a minimum number of objects in the plurality of objects that must each link to each object in the group.

23. The one or more tangible computer-readable storage media as recited in claim 18, wherein a rank is assigned to each object in the second collection of objects, based on which object in the second collection of objects is assigned to a particular concentric portion around the center of the model.

24. A system to mine communities from a plurality of objects, the system comprising:

a processor; and

a memory coupled to the processor, wherein the memory includes one or more instructions that cause the processor to, at least;

identify one or more core object sets from the plurality of objects by identifying one or more objects that are referenced by at least a threshold number of other objects of the plurality of objects, wherein each core object set is incorporated into a respective data structure defining a community; and

for each of the core object sets, expand the respective data structure defining the community to include a set of affiliated objects, wherein the expansion is based on the core object set of the community, and the core object set and the set of affiliated objects are maintained as distinct entities within each respective data structure,

wherein identifying the one or more core object sets comprises;

identifying links between objects of the plurality of objects;

finding groups of objects of the plurality of objects that satisfy a link threshold; and

identifying, as a core object set, one or more of the groups of objects that satisfy the link threshold,

wherein the link threshold is determined by selecting a number of the plurality of objects that is at least 1 percent of the total number of objects in the plurality of objects and multiplying an amplifying frequency factor by a weight sum of all links and dividing it by the number of the plurality of objects selected.

25. The system as recited in claim 24, wherein the one or more instructions further cause the processor to:

repeat the identification and expansion for a plurality of communities of objects, wherein the objects in each community of objects are all from the plurality of objects.

31. The system as recited in claim 24, wherein:

at least two core object sets are identified from the plurality of objects; and

a decision to merge the at least two core object sets is based on a set of conditions comprising a condition specifying that a ratio of a minimum size of one of the at least two core object sets to a size of an intersection of the at least two core object sets is less than 2.

26. A system implemented at least in part in a computing device, the system comprising:

a processor;

a core set identification module to identify core sets of objects for data structures corresponding to communities from a plurality of objects by identifying one or more objects that are referenced by at least a threshold number of other objects of the plurality of objects; and

a community expansion module to expand the data structures corresponding to the communities by adding sets of affiliated objects to the data structures corresponding to the communities, wherein the expansion is based at least in part on at least one core set of objects, and each core set of objects and each set of affiliated objects are maintained as distinct entities within each respective data structure corresponding to a community; and

a core set merging module to merge together a first of the communities and a second of the communities in response to a finding of sufficient similarity between the core objects in the first of the communities and the core objects in the second of the communities,

wherein the finding of sufficient similarity is determined when smallest values from the first of the communities and the second of the communities divided by a set that includes all elements that the first and second communities have in common is less than 2.

27. The system as recited in claim 26, wherein the core set identification module is further to:

identify links between objects of the plurality of objects;

find groups of objects of the plurality of objects that satisfy a link threshold; and

identify, as a core object set, one or more of the groups of objects that satisfy the link threshold.

28. The system as recited in claim 26, wherein the community expansion module is further to:

identify links between objects of the plurality of object;

for each community, identify one or more objects of the plurality of objects, wherein a link exists from each of the identified one or more objects to at least one of the objects of the core object set of the community; and

include, in the set of affiliated objects of the community, each of the identified one or more objects.

29. The system as recited in claim 26, wherein the core set merging module generates a merged community that includes all of the objects of the first of the communities and the second of the communities and has a set of core objects that includes the core objects from the first of the communities and the core objects from the second of the communities.

30. The system as recited in claim 26, further comprising:

a community merging module to merge together a first of the communities and a second of the communities if there is sufficient similarity between the core and affiliated objects of the first of the communities and the core and affiliated objects of the second of the communities.