Re: [networkx-discuss] K_core definition

[Dan Schult]

Could you explain the part you think is incorrect?
Are we not making it sufficiently clear that the degree k must be in the subgraph?
Dan

On Oct 16, 2012, at 10:43 AM, Pol Colomer wrote:

> Hi,
>
> I'm writting because i think that the definition of the k_core in the documentation is wrong.
>
> The correct one is the subgraph of G that all the nodes have k connections inside the subgraph.
>
> Thanks and hope to hear from you soon
>
> Pol Colomer
>
> --
> You received this message because you are subscribed to the Google Groups "networkx-discuss" group.
> To view this discussion on the web visit https://groups.google.com/d/msg/networkx-discuss/-/Xtvac4_5jLoJ.
> To post to this group, send email to networkx...@googlegroups.com.
> To unsubscribe from this group, send email to networkx-discu...@googlegroups.com.
> For more options, visit this group at http://groups.google.com/group/networkx-discuss?hl=en.

[tcb]

Hi,

I think the definition in networkx is fine. The definition of a k-core does not require the nodes be connected in any specific way, just that they have a minimum degree. Are you thinking about the k-corona perhaps?

from networkx:

k_core

(G, k=None, core_number=None)[source]

Return the k-core of G.

A k-core is a maximal subgraph that contains nodes of degree k or more.

This agrees with the standard definitions of the k-core, for example in "Sudden Emergence of a Giant k-core in a Random Graph", Pittel, Spencer and Wormald:

"The k-core of a graph is the largest subgraph with minimum degree at least k." 

-

[Aric Hagberg]

On Tue, Oct 16, 2012 at 9:17 AM, tcb <thecolo...@gmail.com> wrote:
> Hi,
>
> I think the definition in networkx is fine. The definition of a k-core does
> not require the nodes be connected in any specific way, just that they have
> a minimum degree. Are you thinking about the k-corona perhaps?
>
> from networkx:
>

> k_core(G, k=None, core_number=None)[source]

>
> Return the k-core of G.
>
> A k-core is a maximal subgraph that contains nodes of degree k or more.
>
>
> This agrees with the standard definitions of the k-core, for example in
> "Sudden Emergence of a Giant k-core in a Random Graph", Pittel, Spencer and
> Wormald:
>
> "The k-core of a graph is the largest subgraph with minimum degree at least
> k."

We could consider also including a more formal definition with
mathematical notation if that helps.
Aric