Data processing: database and file management or data structures – Database and file access – Preparing data for information retrieval
Reexamination Certificate
2011-06-07
2011-06-07
Rones, Charles (Department: 2164)
Data processing: database and file management or data structures
Database and file access
Preparing data for information retrieval
C707S791000, C707S797000, C707S959000
Reexamination Certificate
active
07958120
ABSTRACT:
Methods and apparatus for a new approach to the problem of finding communities in complex networks relating to a social definition of communities and percolation are disclosed. Instead of partitioning the graph into separate subgraphs from top to bottom a local algorithm (communities of each vertex) allows overlapping of communities. The performance of an algorithm on synthetic, randomly-generated graphs and real-world networks is used to benchmark this method against others. An heuristic is provided to generate a list of communities for networks using a local community finding algorithm. Unlike diffusion based algorithms, The provided algorithm finds overlapping communities and provides a means to measure confidence in community structure. It features locality and low complexity for exploring the communities for a subset of network nodes, without the need for exploring the whole graph.
REFERENCES:
patent: 5581764 (1996-12-01), Fitzgerald et al.
patent: 6038560 (2000-03-01), Wical
patent: 6098064 (2000-08-01), Pirolli et al.
patent: 6233575 (2001-05-01), Agrawal et al.
patent: 6242273 (2001-06-01), Goodwin et al.
patent: 6397682 (2002-06-01), Kumar et al.
patent: 6544357 (2003-04-01), Hehmann et al.
patent: 6665837 (2003-12-01), Dean et al.
patent: 6886129 (2005-04-01), Raghavan et al.
patent: 7031308 (2006-04-01), Garcia-Luna-Aceves et al.
patent: 7051023 (2006-05-01), Kapur et al.
patent: 7483711 (2009-01-01), Burchfiel
patent: 7590589 (2009-09-01), Hoffberg
patent: 7613851 (2009-11-01), Rice et al.
patent: 7689493 (2010-03-01), Sullivan et al.
patent: 7805536 (2010-09-01), Kompella et al.
patent: 2002/0016782 (2002-02-01), Cooper
patent: 2002/0087884 (2002-07-01), Shacham et al.
patent: 2003/0217139 (2003-11-01), Burbeck et al.
patent: 2003/0217140 (2003-11-01), Burbeck et al.
patent: 2003/0220866 (2003-11-01), Pisaria-Henderson et al.
patent: 2004/0064438 (2004-04-01), Kostoff
patent: 2004/0085797 (2004-05-01), Mei et al.
patent: 2004/0093328 (2004-05-01), Damle
patent: 2005/0021531 (2005-01-01), Wen et al.
patent: 2005/0064618 (2005-03-01), Brown et al.
patent: 2005/0113691 (2005-05-01), Liebschner
patent: 2005/0117593 (2005-06-01), Shand
patent: 2005/0160107 (2005-07-01), Liang
patent: 2005/0203838 (2005-09-01), Zhang et al.
patent: 2006/0168065 (2006-07-01), Martin
patent: 2006/0294155 (2006-12-01), Patterson
patent: 2007/0025364 (2007-02-01), Kodialam et al.
patent: 2007/0245035 (2007-10-01), Attaran Rezaei et al.
patent: 2008/0232809 (2008-09-01), Beshai et al.
patent: 2009/0046678 (2009-02-01), Lee et al.
patent: 2009/0086663 (2009-04-01), Ho et al.
patent: 2009/0157855 (2009-06-01), Adam et al.
patent: 2009/0168768 (2009-07-01), Chiabaut et al.
patent: 2009/0265475 (2009-10-01), Fujita
patent: 2009/0296719 (2009-12-01), Maier et al.
Kimberly Patch, Simple search lightens Net load, 2004, TRN, pp. 1-3.
Roychowdhury et al., Scalable Percolation Search in Power Law Networks, Jun. 2004, Department of Electrical Engineering, University of California, Los Angeles, pp. 1-13.
Chung et. al., The Small World Phenomenon in Hybrid Power Law Graphs, 2004, pp. 1-16.
Baxter et. al., Generalised percolation probabilities for the self-dual Potts model, Apr. 1987, pp. 1-10.
Lyons, Probability on Trees and Networks, Apr. 17, 2005, pp. 1-53.
Manku et. al., Know thy Neighbor: the Power of Lookahead in Randomized P2P Networks, Jun. 2004, pp. 1-10.
Meester et. al., Navigation in small world networks, a scale-free continuim model, Jul. 2003, pp. 1-9.
Golbeck, Accuracy of Metrics for Inferring Trust and Reputation in Semantic Web-based Social Networks, Apr. 2004, pp. 1-11.
International Search Report for PCT Application No. PCT/US06/14160 dated Sep. 4, 2007.
Bela Bollobas, “Random Graphs,” Second Edition, Cambridge University Press, United Kingdom, 2001, Chapter 1 and 2 (pp. 1-59).
John Scott, “Social Network Analysis: A Handbook,” 2ndEdition, Sage Publications, London, 2000, Chapter 4 (pp. 63-81).
Stanley Wasserman, et al., “Social Network Analysis: Methods and Applications”, Cambridge University Press, Cambridge, England, 1994, pp. 17-20 and Chapter 7 (pp. 249-290).
James P. Bagrow, et al., “A Local Method for Detecting Communities,” Physical Review E, vol. 72, No. 4, 2005, 046108.
Riccardo Boscolo, et al., “Functionality Encoded in Topology? Discovering Macroscopic Regulatory Modules from Large-Scale Protein-DNA Interaction Networks,” Reprint arXiv:q-bio/0501039, Jan. 2005.
Aaron Clauset, et al., “Finding community structure in very large networks,” Physical Review E, vol. 70, No. 6, Dec. 2004, 066111.
P. Erdos, et al., “On the Evolution of Random Graphs,” Publication of the Mathematical Institute of the Hungarian Academy of Sciences, vol. 5, 1960.
P. Erdos, et al., “On the Strength of Connectedness of a Random Graph,” Acta Mathematica Scientia Hungarica, vol. 12, Nos. 1-2, 1961, pp. 261-267.
Gary William Flake, et al., “Self-Organization and Identification of Web Communities,” IEEE Computer Society, vol. 35, Issue 3, Mar. 2002, pp. 66-71.
Laura Garton, et al., “Studying On-Line Social Networks,” In Doing Internet Research, S. Jones, Ed. Sage, Thousand Oaks, Calif., 1999, pp. 75-105.
Michelle Girvan, et al., “Community structure in social and biological networks,” PNAS, vol. 99, No. 12, Jun. 2002, pp. 7821-7826.
Pascal Pons, et al., “Computing communities in large networks using random walks,” ArXiv Condensed Matter e-prints, Dec. 2004.
Jesus M. Gonzalez-Barahona, et al., “Community structure of modules in the apache project,” In MSR '05: Proceedings of the 2005 international workshop on Mining software repositories, 2005.
M. E. J. Newman, “Fast algorithm for detecting community structure in networks,” Physical Review E 69, Jun. 6, 2004, 066133.
M. E. J. Newman, “Coauthorship Networks and Patterns of Scientific Collaboration,” PNAS, vol. 101, Apr. 2004, pp. 5200-5205.
Alex Pothen, et al., “Partitioning Sparse Matrices with Eigenvectors of Graphs,” Society of Industrial and Applied Mathematics, SIAM Journal on Matrix Analysis and Applications, vol. 11, No. 3, Jul. 1990, pp. 430-452.
Filippo Radicchi, et al., “Defining and identifying communities in networks,” PNAS, vol. 101, No. 9, Mar. 2004, pp. 2658-2663.
Alexander W. Rives, et al., “Modular organization of cellular networks,” PNAS, vol. 100, No. 3, Feb. 2003, pp. 1128-1133.
Barry Wellman, et al., “Computer Networks as Social Networks: Collaborative Work, Telework, and Virtual Community,” Annual Reviews Sociology, vol. 22, No. 1, 1996, pp. 213-238.
F. Wu, et al., “Finding communities in linear time: a physics approach,” The European Physical Journal B, vol. 38, No. 2, 2004, pp. 331-338.
Wayne W. Zachary, “An Information Flow Model for Conflict and Fission in Small Groups,” Journal of Anthropological Research, vol. 33, No. 4, Winter, 1977, pp. 452-473.
B. W. Kernighan, et al., “An Efficient Heuristic Procedure for Partitioning Graphs,” The Bell System Technical Journal 49, Feb. 1970, pp. 291-307.
First Office Action dated Sep. 11, 2009 for Chinese Patent Application No. 200680025190.6.
Second Office Action dated Jun. 3, 2010 for Chinese Patent Application No. 200680025190.6.
Attaran Rezaei Behnam
Muntz Alice Hwei-Yuan Meng
Hayes Jennifer
Mahmood Rezwanul
Netseer, Inc.
Nixon & Peabody LLP.
Rones Charles
LandOfFree
Method and apparatus for distributed community finding does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Method and apparatus for distributed community finding, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and apparatus for distributed community finding will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2730224