Community mining based on core objects and affiliated objects

• US 20050021531A1
• Filed: 07/22/2003
• Published: 01/27/2005
• Est. Priority Date: 07/22/2003
• Status: Active Grant

• 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
• Granted Patent: US 7,885,960 B2
• Time in Patent Office: Days
• US Class Current: 1/1
• 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 computerized method comprising:

identifying, from a plurality of objects, a set of core objects for a community of objects; and

expanding, based on the set of core objects, the community of objects to include a set of affiliated objects.

2. A 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. A 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 objects in the first community and the core objects in the second community, 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. A 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. A 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. A 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. A 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. A 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. A method as recited in claim 1, wherein identifying the set of core objects for 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 core set, one or more of the groups of objects that satisfy the link threshold.

10. A method as recited in claim 9, 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.

11. A method as recited in claim 1, wherein expanding 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.

12. A method as recited in claim 11, further comprising:

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

ranking each affiliated object in the set of affiliated objects; and

assigning each affiliated object in the set of affiliated objects to a particular concentric portion around the center of the model in accordance with the rank of the affiliated object.

13. A method as recited in claim 11, 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.

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

15. A 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 citation in one document to another document.

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

17. A 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 relationship of one person to another person.

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

19. A method as recited in claim 18, 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.

20. One or more computer readable 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; and

add, to the community, the second collection of objects.

21. One or more computer readable media as recited in claim 20, wherein each object of the second collection of objects is an affiliated object of the community.

22. One or more computer readable media as recited in claim 20, 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; and

add, to the additional communities, the additional second collections of objects.

23. One or more computer readable media as recited in claim 22, 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 objects in the first of the communities and the core objects in the second of the communities, 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.

24. One or more computer readable media as recited in claim 22, 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.

25. One or more computer readable media as recited in claim 20, wherein the instructions that, when executed by the one or more processors, cause the one or more processors to identify the first collection of objects comprise instructions that, when executed by the one or more processors, cause the one or more processors 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 the core of the community, one of the groups of objects that satisfy the link threshold.

26. One or more computer readable media as recited in claim 22, 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.

27. One or more computer readable media as recited in claim 20, wherein the instructions that, when executed by the one or more processors, cause the one or more processors to identify the second collection of objects comprise instructions that, when executed by the one or more processors, cause the one or more processors to:

identify links between objects of the plurality of objects;

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 first collection of objects; and

include, in the second collection of objects, each of the identified one or more objects.

28. One or more computer readable media as recited in claim 20, wherein the plurality of instructions, when executed by the one or more processors, further cause the one or more processors to:

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

rank each object of the second collection of objects; and

assign each object of the second collection of objects to a particular concentric portion around the center of the model in accordance with the rank of the object.

29. 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;

identify, from the plurality of objects, one or more core object sets from the plurality of objects, wherein each core object set is a core of a community; and

for each of the core object sets, expand the community to include a set of affiliated objects, wherein the expansion is based on the core object set of the community.

30. A system as recited in claim 29, 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. A system as recited in claim 29, wherein the one or more instructions that cause the processor to identify the one or more core object sets comprises one or more instructions that cause the processor 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.

32. A system as recited in claim 29, wherein the one or more instructions that cause the processor to expand the community comprises one or more instructions that cause the processor to:

identify links between objects of the plurality of objects; and

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.

33. A system comprising:

a core set identification module to identify core sets of objects for communities from a plurality of objects; and

a community expansion module to expand communities by adding affiliated objects to the communities, wherein the expansion of a community is based at least in part on the core set of objects of the community and links from objects of the plurality of objects to the core set of objects of the community.

34. A system as recited in claim 33, 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.

35. A system as recited in claim 33, wherein the community expansion module is further to:

identify links between objects of the plurality of objects; and

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.

36. A system as recited in claim 33, further comprising:

a core set merging module to merge together a first of the communities and a second of the communities if there is sufficient similarity between the core objects in the first of the communities and the core objects in the second of the communities, 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.

37. A system as recited in claim 33, 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.

38. A method comprising:

grouping a first collection of a plurality of objects into a center portion;

grouping a second collection of the plurality of objects into one or more concentric portions around the center portion; and

identifying, as the community of objects, the groupings of the first and second collections of the objects.

39. A method as recited in claim 38, wherein both the center portion and the one or more concentric portions collectively are a set of concentric circles.

40. A method as recited in claim 38, wherein the center portion comprises a circle.

41. A method as recited in claim 38, wherein the one or more concentric portions each comprise a circle.

42. A method as recited in claim 38, wherein the first collection of the objects comprises a core set of objects.

43. A method as recited in claim 38, wherein each object of the second collection of the objects comprises an affiliated object.

44. One or more computer readable 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 describe a community of objects by:

creating a set of concentric circles;

assigning a group of core objects of the community to the center circle of the set of concentric circles; and

assigning a group of affiliated objects of the community to one or more circles of the set of concentric circles, wherein the one or more circles surround the center circle.